662.maximum-width-of-binary-tree.md

662. Maximum Width of Binary Tree

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
         6
       /   \
      9     8
     /     / 
    1     0
Output: 2

Input: 
         6
       /   \
      9     8
     /       \ 
    1         0
Output: 4

Edge / Corner Cases

• The tree contains only one node at some levels.

Input:
         6
       /   \
      9      8   
     /     
    1           

• The maximum width is located at one of the subtree.

Input: 
           6
        /     \
       9       8   
    /     \      \
   1       0     10
         /   \     \
        6     7     9 
       /       \
      ...      ...
     ...        ...
    /             \
   1               0

BFS with Index

We use index to calculate the width, the index starts from 0, the index of left child will be the root index * 2 + 1, right will be root index * 2 + 2 (The same idea of array index from heap).

For example, the width at each level is:

// Index        // Tree
      0              6
    /   \          /   \
   1     2        9     8
  / \   / \      /     / 
 3   4 5   6    1     0

• Level 0: 1
• Level 1: 2 - 1 + 1
• Level 2: 5 - 3 + 1

// Index        // Tree
      0              6
    /   \          /   \
   1     2        9     8
  / \   / \      /       \ 
 3   4 5   6    1         0

• Level 0: 1
• Level 1: 2 - 1 + 1 = 2
• Level 2: 6 - 3 + 1 = 4

So the width at that level is the index of last node - the index of first node + 1. We use a queue to store the node and its index, and we iterate the queue to calculate the width.

fun widthOfBinaryTree(root: TreeNode?): Int {
    if (root == null) return 0
    var maxWidth = 0
    // Node with its index
    val queue = ArrayDeque<Pair<TreeNode, Int>>()
    queue.addLast(root to 0)
    while (queue.isNotEmpty()) {
        val size = queue.size
        
        var startIndex = 0
        var endIndex = 0
        for (i in 0 until size) {
            val pair = queue.removeFirst()
            val node = pair.first
            val index = pair.second
            
            if (i == 0) startIndex = index
            if (i == size - 1) endIndex = index
            
            if (node.left != null) queue.addLast(node.left to 2 * index + 1)
            if (node.right != null) queue.addLast(node.right to 2 * index + 2)
        }
        
        maxWidth = max(maxWidth, endIndex - startIndex + 1)
    }
    return maxWidth
}

• Time Complexity: O(n).
• Space Complexity: O(n).

DFS

We use the same indexing mechanism as BFS, and we use a map to store the leftmost index of each level. For each node, we calculate the width by comparing the current index with the leftmost index of that level.

private val levelMin = HashMap<Int, Int>()
private var currentLevel = 0
private var maxWidth = 0

fun widthOfBinaryTree(root: TreeNode?): Int {
    dfs(root, 0, 1)
    return maxWidth
}

private fun dfs(root: TreeNode?, index: Int, level: Int) {
    if (root == null) return

    if (!levelMin.containsKey(level)) {
        levelMin[level] = index
    }

    maxWidth = maxOf(maxWidth, index - levelMin[level]!! + 1)

    dfs(root.left, index * 2 + 1, level + 1)
    dfs(root.right, index * 2 + 2, level + 1)
}

• Time Complexity: O(n).
• Space Complexity: O(n).