Finding Maximum Width of Binary Search Tree

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

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