Maximum Width of Binary Tree

LeetCode Q 662- Maximum Width of Binary Tree

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

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

Solution:

We enhance the node TreeNode with an index, indicating its position in a layer. We do the BFS traversing the tree from layer to layer. On each layer, find the difference between indexes of the left most not-null node and right most not-null node. If we cannot find a not-null node, we finish our traverse.

Code:

class Pair {
  int index;
  TreeNode node;
  public Pair(TreeNode node, int index) {
    this.index = index; this.node = node;
  }
}
public int widthOfBinaryTree(TreeNode root) {
  int res = 0;

  Queue<Pair> que = new LinkedList<>();
  que.offer(new Pair(root, 0));

  while (!que.isEmpty()) {
    int left = -1, right = -1;
    int size = que.size();
    for (int i = 0; i < size; i++) {
      Pair p = que.poll();
      if (p.node == null) continue;
      if (left == -1) left = p.index;
      right = p.index;
      que.offer(new Pair(p.node.left, 2 * index));
      que.offer(new Pair(p.node.right, 2 * index + 1)); 
    }
    if (left == -1) break;
    res = Math.max(res, right - left + 1);
  }

  return res;
}