Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2*i and 2*i + 1. The idea is to use a HashMap to record the the indices of all the nodes of the Tree using a DFS.

Now use BFS to traverse each level of the tree. For each level of the tree, the width is (last_index - first_index + 1). Then, we just need to find the maximum width.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        
        if(root == null){
            return 0;
        }
        Map<TreeNode, Integer> nodeIndexMap = new HashMap<>();
        nodeIndexMap.put(root, 1);
        DFS(root, nodeIndexMap);
        
        int cur_width = 0;
        int max_width = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int first_index = 0;
            int last_index = 0;
            int cur_level_size = queue.size();
            for(int i = 0 ; i < cur_level_size ; i++){
                TreeNode curNode = queue.poll();
                if(i == 0){
                    first_index = nodeIndexMap.get(curNode);
                }
                if( i == cur_level_size - 1){
                   last_index = nodeIndexMap.get(curNode);
                }
                if(curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
            }
            cur_width =  (last_index - first_index + 1);
            max_width = Math.max(cur_width, max_width);
        }
        return max_width;
    }
    
    private void DFS(TreeNode node, Map<TreeNode, Integer> nodeIndexMap){
        if(node == null){
            return;
        }
        int cur_index = nodeIndexMap.get(node);
        if(node.left != null){
            nodeIndexMap.put(node.left, (cur_index * 2));
        }
        if(node.right != null){
            nodeIndexMap.put(node.right, (cur_index * 2 + 1));
        }
        DFS(node.left, nodeIndexMap);
        DFS(node.right, nodeIndexMap);
    }
}

Let N be the total number of nodes in the input tree.

  • Time Complexity: O(N) + O(N) = O(N)
    • We visit each node once for DFS. And at each visit, it takes a constant time to process – O(N)
    • We visit each node once for BFS. And at each visit, it takes a constant time to process – O(N)

Space Complexity: O(N)

  • We have used an additional HashMap to keep the indices of all the nodes. As a result, the space complexity of the table would be O(N).
  • Since we implement DFS traversal with recursion which would incur some additional memory consumption in the function call stack, we need to take this into account for the space complexity.
  • The consumption of function stack is proportional to the depth of recursion. Again, in the same worst case above, where the tree is extremely skewed, the depth of the recursion would be equal to the number of nodes in the tree. Therefore, the space complexity of the function stack would be O(N).
  • We have also used a Queue for the BFS and as a result, the space complexity of the Queue would be O(N).
  • To sum up, the overall space complexity of the algorithm is O(N) + O(N) = O(N)

Categories: Binary Tree

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s