943,603 Members | Top Members by Rank

Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 3702
  • C++ RSS
Mar 19th, 2008
0

Finding Maximum Width of Binary Search Tree

Expand Post »
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..
Reputation Points: 10
Solved Threads: 0
Newbie Poster
noktasizvirgul is offline Offline
13 posts
since Mar 2008
Mar 19th, 2008
0

Re: Finding Maximum Width of Binary Search Tree

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.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: can't find the problem after checking my similar programs
Next Thread in C++ Forum Timeline: how to code ATM for banks





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC