662. Maximum Width of Binary Tree #

Problem #

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

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.

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

Note: Answer will in the range of 32-bit signed integer.

Problem Summary #

Given a binary tree, write a function to get the maximum width of this tree. The width of the tree is the maximum width among all levels. This binary tree has the same structure as a full binary tree, but some nodes are null.

The width of each level is defined as the length between two end nodes (the leftmost and rightmost non-null nodes at that level; the null nodes between the two end nodes are also counted in the length).

Note: The answer is within the range of a 32-bit signed integer.

Solution Approach #

Given a binary tree, find the widest part of the tree.
This problem can be solved with either BFS or DFS, but BFS is more convenient. Traverse level by level, and compute the leftmost non-null node and the rightmost non-null node for each level. Everything between these two nodes is counted as the width. Finally, output the maximum width. The key to this problem is how to efficiently find the left and right boundaries of each level.
Some people may think of first completing the full binary tree and then finding the left and right boundaries for each level separately. After submission, this method will get stuck on the 104 / 108 test case. This test case causes the full binary tree nodes filled in the last few levels to be especially numerous, eventually leading to Memory Limit Exceeded.
Since this problem needs to find the left and right boundaries of each level, the Val value of each node is actually irrelevant to us. We can use this value as an index, marking the position of the node in each level. If the parent node’s index in the previous level is x, then its left child’s index in the next level’s full binary tree is 2*x, and its right child’s index in the next level’s full binary tree is 2*x + 1. Assign indices to all nodes, use BFS level-order traversal for each level, find the left and right boundaries for each level, subtract them to get the width, and dynamically maintain the maximum width. This is the final answer to the problem.

Code #


package leetcode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	}

	queue, res := []*TreeNode{}, 0
	queue = append(queue, &TreeNode{0, root.Left, root.Right})

	for len(queue) != 0 {
		var left, right *int
		// Note here: save the length of queue first; this is equivalent to getting the total number of nodes at this level
		qLen := len(queue)
		// Do not write i < len(queue) in this loop, because the length of queue decreases on each iteration
		for i := 0; i < qLen; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				// According to the parent-child relationship in a full binary tree, get the next-level node's index in that level
				newVal := node.Val * 2
				queue = append(queue, &TreeNode{newVal, node.Left.Left, node.Left.Right})
				if left == nil || *left > newVal {
					left = &newVal
				}
				if right == nil || *right < newVal {
					right = &newVal
				}
			}
			if node.Right != nil {
				// According to the parent-child relationship in a full binary tree, get the next-level node's index in that level
				newVal := node.Val*2 + 1
				queue = append(queue, &TreeNode{newVal, node.Right.Left, node.Right.Right})
				if left == nil || *left > newVal {
					left = &newVal
				}
				if right == nil || *right < newVal {
					right = &newVal
				}
			}
		}
		switch {
		// If a level has only one node, then the width of this level is 1
		case left != nil && right == nil, left == nil && right != nil:
			res = max(res, 1)
		// If a level has two nodes, then the width of this level is the distance between the two nodes
		case left != nil && right != nil:
			res = max(res, *right-*left+1)
		}
	}
	return res
}