Finding Maximum Width of Binary Search Tree

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 456,453 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,639 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Please support our C++ advertiser: Programming Forums

Thread Tools Display Modes

Views: 827 | Replies: 1

•

Join Date: Mar 2008

Posts: 7

Reputation: noktasizvirgul is an unknown quantity at this point

Rep Power: 0

Solved Threads: 0

noktasizvirgul noktasizvirgul is offline

Offline

Newbie Poster

Finding Maximum Width of Binary Search Tree

Mar 19th, 2008

Dear all,
I need to find the max width of Binary Search Tree. It means the biggest number of nodes in a level among all levels.

http://www.imgloadtr.com/pics/aca410...5721df328a.jpg

In the figure the maximum width is 4, since level 3 has the biggest number of nodes, which is 4.

I will be grateful, if you help me..

•

Join Date: Sep 2004

Posts: 6,515

Reputation: Narue has much to be proud of

Rep Power: 31

Solved Threads: 488

Narue

Offline

Expert Meanie

Re: Finding Maximum Width of Binary Search Tree

Mar 19th, 2008

I can think of two simple solutions off the top of my head:

1) Allocate an array of N, where N is the number of nodes in the tree. Then traverse the tree and save the level of each node in the array as you go. Sort the array and the longest run will be the level with the most nodes.

2) Perform a level-order traversal of the tree and count how many nodes are on each level. Save the largest value as you go down, and when you get to the end, you'll have the level with the most nodes.

I'm here to prove you wrong.