Member Avatar for noktasizvirgul

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.

[IMG]http://www.imgloadtr.com/pics/aca41035095c6695489f975721df328a.jpg[/IMG]

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..

  • 2 Contributors
  • 1 Reply
  • 178 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Narue
Member Avatar for Narue

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.