Maximum Width of Binary Tree

📋

Maximum Width of Binary Tree

Edge cases:

</>

IDE

def widthOfBinaryTree(root: Optional[TreeNode]) -> int:public int widthOfBinaryTree(TreeNode root)int widthOfBinaryTree(TreeNode* root)function widthOfBinaryTree(root)

def widthOfBinaryTree(root):
    # Write your solution here
    pass

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int widthOfBinaryTree(TreeNode* root) {
    // Write your solution here
    return 0;
}

function widthOfBinaryTree(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Width calculated as number of non-null nodes at levelIgnoring null nodes between leftmost and rightmost nodes, thus undercounting width.✅ Track node indices during BFS and compute width as last_index - first_index + 1 including null gaps.

Wrong: Width off by one (e.g., 3 instead of 4)Calculating width as last_index - first_index instead of last_index - first_index + 1.✅ Add +1 when computing width at each level.

Wrong: Runtime error or wrong width on deep treesInteger overflow in node indexing for very deep trees.✅ Normalize indices per level by subtracting first index and use 64-bit integers for indexing.

Wrong: Timeout on large inputUsing exponential or recursive approach instead of BFS with index normalization.✅ Implement BFS with index normalization for O(n) time complexity.

Wrong: Returns 0 for single node treeNot handling base case when root is not null.✅ Return 1 if root is not null.

✓

Test Cases

Focus on handling base cases like empty and single-node trees correctly.

Consider tricky cases with sparse trees and indexing overflow.

Optimize your BFS approach to handle large inputs efficiently.

t1_01basic

Input{"root":[1,3,2,5,3,null,9]}

Expected4

⏱ Performance - must finish in 2000ms

The third level has nodes 5,3,null,9. The width is 4 including the null node.

💡 Use BFS to traverse the tree level by level.

💡 Track the index positions of nodes to calculate width including nulls.

💡 Width at each level = last_index - first_index + 1; update max width accordingly.

Why it failed: Incorrect width calculation: likely not accounting for null nodes between leftmost and rightmost nodes. Fix by tracking node indices and computing width as last_index - first_index + 1.

✓ Correctly computes width using BFS with indexing.

t1_02basic

Input{"root":[1,3,2,5,null,null,9,6,null,null,7]}

Expected8

⏱ Performance - must finish in 2000ms

The fourth level has nodes 6,null,null,null,null,null,null,7, width is 8 including nulls.

💡 Remember to assign indices to nodes even if some children are missing.

💡 Use BFS with index normalization to avoid integer overflow.

💡 Calculate width as last_index - first_index + 1 at each level.

Why it failed: Fails to handle sparse levels with many nulls; likely missing index normalization or skipping nulls. Fix by normalizing indices per level and counting null gaps.

✓ Handles sparse levels correctly with index-based width calculation.

t2_01edge

Input{"root":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree has width 1.

💡 Check behavior when tree has only one node.

💡 Width should be 1 since only one node exists at level.

💡 Ensure code handles single-node trees without errors.

Why it failed: Returns 0 or error on single node tree; fix by returning 1 when root is not null.

✓ Correctly returns width 1 for single node tree.

t2_02edge

Input{"root":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree has width 0.

💡 Check behavior when tree is empty (null root).

💡 Width should be 0 for empty tree.

💡 Return 0 immediately if root is null.

Why it failed: Fails or crashes on empty tree input; fix by checking if root is null and returning 0.

✓ Correctly returns 0 for empty tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected1

⏱ Performance - must finish in 2000ms

Tree with only left children has width 1 at every level.

💡 Test trees skewed to one side only.

💡 Width should always be 1 if only one node per level.

💡 Ensure code does not count null siblings as width.

Why it failed: Incorrectly counts null siblings causing width > 1; fix by tracking indices properly and not counting missing siblings as nodes.

✓ Correctly computes width 1 for left-skewed tree.

t2_04edge

Input{"root":[1,null,2,null,3,null,4,null,5]}

Expected1

⏱ Performance - must finish in 2000ms

Tree with only right children has width 1 at every level.

💡 Test trees skewed to the right only.

💡 Width should always be 1 if only one node per level.

💡 Ensure code does not count null siblings as width.

Why it failed: Incorrectly counts null siblings causing width > 1; fix by tracking indices properly and not counting missing siblings as nodes.

✓ Correctly computes width 1 for right-skewed tree.

t3_01corner

Input{"root":[1,3,2,5,null,null,9,6,null,null,7]}

Expected8

⏱ Performance - must finish in 2000ms

Tests correct handling of sparse tree with nulls between nodes at a level.

💡 Beware of greedy approaches that only count non-null nodes.

💡 Use BFS with index tracking to include null gaps.

💡 Normalize indices per level to avoid overflow and calculate width correctly.

Why it failed: Greedy approach fails by counting only non-null nodes, missing null gaps. Fix by using BFS with index-based width calculation including nulls.

✓ Correctly handles sparse levels with null gaps.

t3_02corner

Input{"root":[1,3,2,5,3,null,9,6,null,null,7,null,null,null,15]}

Expected8

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in width calculation with deep sparse tree.

💡 Check if width calculation uses inclusive indices (last - first + 1).

💡 Verify BFS indexing and normalization at each level.

💡 Fix off-by-one by adding +1 when computing width.

Why it failed: Off-by-one error in width calculation (missing +1). Fix by computing width as last_index - first_index + 1.

✓ Correctly computes width with inclusive indexing.

t3_03corner

Input{"root":[1,3,2,5,3,null,9,6,null,null,7]}

Expected8

⏱ Performance - must finish in 2000ms

Tests integer overflow risk in indexing for very deep trees.

💡 Use index normalization at each level to prevent overflow.

💡 Use long or 64-bit integers for indexing in languages that require it.

💡 Normalize indices by subtracting the first index of the level.

Why it failed: Integer overflow in indexing causes wrong width or runtime error. Fix by normalizing indices per level and using 64-bit integers.

✓ Correctly handles indexing without overflow.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Complete binary tree with 100 nodes; BFS O(n) must complete within 2 seconds.

💡 Use BFS with index normalization for O(n) time complexity.

💡 Avoid recursive DFS to prevent stack overflow.

💡 Use efficient queue data structures like deque.

Why it failed: TLE due to exponential or inefficient approach; fix by using BFS with index normalization and O(n) complexity.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given a binary tree and need to count nodes that are "good" -- nodes whose value is greater than or equal to all values on the path from the root to that node. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy traversal that counts nodes greater than their immediate parent only

B. Depth-first search (DFS) or breadth-first search (BFS) that tracks the maximum value seen on the path to each node

C. Dynamic programming with memoization storing counts for subtrees

D. Sorting nodes by value and then counting based on sorted order

Solution

1. Step 1: Understand the problem requirement

   The problem requires comparing each node's value to all values on the path from the root, not just its parent.

2. Step 2: Identify the approach that tracks path state

   Only DFS or BFS that carries the maximum value seen so far on the path can correctly determine if a node is "good".

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking max value on path ensures correct counting [OK]

Hint: Track max value on path, not just parent [OK]

Common Mistakes:

• Only compare node to parent, missing path max
• Trying DP without path state
• Sorting nodes loses tree structure

2. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

3. Identify the bug in the following near-correct implementation of the optimal zigzag level order traversal:

def zigzagLevelOrder(root):
    if not root:
        return []
    currentLevel = [root]
    nextLevel = []
    result = []
    left_to_right = True
    while currentLevel:
        level_vals = []
        while currentLevel:
            node = currentLevel.pop()
            level_vals.append(node.val)
            if left_to_right:
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            else:
                if node.right:
                    nextLevel.append(node.right)
                if node.left:
                    nextLevel.appen(node.left)  # typo here
        result.append(level_vals)
        currentLevel, nextLevel = nextLevel, []
        left_to_right = not left_to_right
    return result

medium

A. Line 'result.append(level_vals)' should reverse level_vals before appending

B. Line with 'nextLevel.appen(node.left)' has a typo causing runtime error

C. Line 'left_to_right = not left_to_right' should be before swapping stacks

D. Line 'currentLevel.pop()' should be 'currentLevel.pop(0)' to pop from front

Solution

1. Step 1: Locate suspicious line

   The line 'nextLevel.appen(node.left)' contains a typo: 'appen' instead of 'append'.

2. Step 2: Understand impact

   This typo causes a runtime AttributeError, breaking the code during execution.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Typo in method name -> runtime error [OK]

Hint: Check method names carefully for typos [OK]

Common Mistakes:

• Forgetting to reverse levels
• Popping from wrong end
• Misplacing direction toggle

4. What is the time complexity of the optimal iterative BFS approach using two queues for N-ary tree level order traversal, where n is the number of nodes in the tree?

medium

A. O(n) because each node is visited exactly once

B. O(n²) because each node's children are enqueued multiple times

C. O(n log n) due to sorting nodes at each level

D. O(n + m) where m is the maximum number of children per node

Solution

1. Step 1: Identify operations per node

   Each node is enqueued and dequeued exactly once, and its children are iterated once.

2. Step 2: Sum over all nodes

   Since total nodes are n, total operations scale linearly with n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal visits each node once -> O(n) time [OK]

Hint: BFS visits each node once, no repeated work [OK]

Common Mistakes:

• Assuming children are enqueued multiple times causing O(n²)

5. Suppose the problem is extended so that node values can be negative and the tree can contain duplicate values. Which modification to the iterative DFS approach is necessary to correctly count good nodes?

hard

A. Initialize max_val with negative infinity instead of root.val to handle negative values

B. Use BFS instead of DFS to ensure correct max_val tracking

C. Skip nodes with duplicate values to avoid double counting

D. Track max_val per path and update it before pushing children, no other changes needed

Solution

1. Step 1: Consider negative and duplicate values impact

   Negative values do not affect logic if max_val is tracked per path; duplicates are allowed as long as comparison is >=.

2. Step 2: Confirm max_val update timing

   Updating max_val before pushing children ensures correct max_val state per path, no need to initialize differently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Maintaining max_val per path handles negatives and duplicates correctly [OK]

Hint: Keep max_val updated per path, no special init needed [OK]

Common Mistakes:

• Initializing max_val incorrectly
• Switching traversal unnecessarily
• Skipping duplicates incorrectly