Find maximum width of given binary tree

Given a binary tree, write an efficient algorithm to compute maximum width of it.

 

For example, the maximum width of below tree is 4

 
maximum width

 


 

1. Iterative Approach

 

In iterative version, we perform level order traversal of the tree. We can easily modify level order traversal to maintain maximum number of nodes in current level. Then the width of the tree is equal to maximum number of nodes in any level in the tree.

C++

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n) for queue.

 


 

2. Recursive Approach

 

We can also solve this problem recursively by using hashing. We traverse the tree in preorder fashion and store count of nodes present in each level in a map. Finally, we traverse the map and return maximum value found.

Please note that we can also traverse the tree in inorder or postorder fashion.

C++

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Nilesh
Guest
Nilesh

+1