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

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

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

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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂