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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Nilesh
Guest
Nilesh

+1

wpDiscuz