Minimum Depth of Binary Tree

🎯

Minimum Depth of Binary Tree

easyTREEAmazonFacebook

Imagine you want to find the shortest path to safety in a maze represented as a binary tree, where each node is a room and the exit is a leaf node. Finding the minimum depth is like finding the quickest escape route.

💡 This problem asks for the shortest distance from the root to the nearest leaf node in a binary tree. Beginners often confuse minimum depth with maximum depth or fail to handle nodes with only one child correctly, which leads to incorrect answers.

📋

Problem Statement

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children.

The number of nodes in the tree is in the range [1, 10^5]Node values can be any integerThe tree is not necessarily balanced

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Output2

The shortest path to a leaf is from 3 to 9, which has length 2.

Input"root = [2,null,3,null,4,null,5,null,6]"

Output5

The tree is skewed to the right; minimum depth equals the length of the only path.

• Single node tree → minimum depth is 1
• Tree where root has only one child → minimum depth is depth of that child subtree
• Tree with multiple leaves at different depths → minimum depth is the smallest among them
• Tree with null root → minimum depth is 0

⚠️

Common Mistakes

Returning min(left_depth, right_depth) + 1 without checking for null children

Incorrect minimum depth when one child is missing, often returns 1 instead of correct depth

✅ Add explicit checks for null left or right child and return depth of the non-null subtree plus one

Confusing minimum depth with maximum depth

Returns the longest path instead of shortest, failing the problem requirement

✅ Ensure to use min() function and stop at first leaf in BFS

Not stopping BFS at first leaf node

BFS continues unnecessarily, wasting time and losing optimality

✅ Return immediately when a leaf node is dequeued in BFS

Using DFS without pruning on very deep trees

Stack overflow or timeout due to deep recursion

✅ Use BFS or add pruning to DFS to limit recursion depth

Assuming leaf nodes always have two children null

Misidentifies leaf nodes if tree has nodes with only one child

✅ Check both left and right children are null to confirm leaf

🧠

Brute Force (Pure Recursion)

💡 This approach is the most straightforward and helps understand the problem deeply by exploring all paths. It is simple but inefficient for large trees due to repeated computations and deep recursion.

Intuition

Recursively compute the minimum depth of left and right subtrees, then take the smaller one plus one for the current node. Special care is needed when one child is missing.

Algorithm

1. If the current node is null, return 0.
2. If the node is a leaf (no children), return 1.
3. Recursively find the minimum depth of left and right subtrees.
4. If one subtree is missing, return the depth of the other subtree plus one.
5. Otherwise, return the minimum of the two depths plus one.

💡 The tricky part is handling nodes with only one child correctly, which is often overlooked.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    if not root.left:
        return minDepth(root.right) + 1
    if not root.right:
        return minDepth(root.left) + 1
    return min(minDepth(root.left), minDepth(root.right)) + 1

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(minDepth(root))  # Output: 2

Line Notes

if not root:Base case: empty tree has depth 0 to stop recursion

if not root.left and not root.right:Leaf node found, so minimum depth is 1 here

if not root.left:If left subtree is missing, must consider right subtree only to avoid incorrect min

return min(minDepth(root.left), minDepth(root.right)) + 1Return minimum depth of both subtrees plus current node to build depth

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.minDepth(root)); // Output: 2
    }
}

Line Notes

if (root == null) return 0;Empty tree base case to stop recursion

if (root.left == null && root.right == null) return 1;Leaf node base case with depth 1

if (root.left == null) return minDepth(root.right) + 1;Handle missing left subtree to avoid wrong min

return Math.min(minDepth(root.left), minDepth(root.right)) + 1;Return minimum depth plus current node

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    if (!root->left) return minDepth(root->right) + 1;
    if (!root->right) return minDepth(root->left) + 1;
    return min(minDepth(root->left), minDepth(root->right)) + 1;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << minDepth(root) << endl; // Output: 2
    return 0;
}

Line Notes

if (!root) return 0;Base case: empty tree stops recursion

if (!root->left && !root->right) return 1;Leaf node base case with depth 1

if (!root->left) return minDepth(root->right) + 1;If left subtree missing, recurse right only to avoid wrong min

return min(minDepth(root->left), minDepth(root->right)) + 1;Return minimum depth plus current node

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function minDepth(root) {
    if (!root) return 0;
    if (!root.left && !root.right) return 1;
    if (!root.left) return minDepth(root.right) + 1;
    if (!root.right) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(minDepth(root)); // Output: 2

Line Notes

if (!root) return 0;Empty tree base case to stop recursion

if (!root.left && !root.right) return 1;Leaf node base case with depth 1

if (!root.left) return minDepth(root.right) + 1;Handle missing left subtree to avoid incorrect min

return Math.min(minDepth(root.left), minDepth(root.right)) + 1;Return minimum depth plus current node

⏱

Complexity

TimeO(n)

SpaceO(h) where h is tree height due to recursion stack

Each node is visited once, so time is linear. Space depends on recursion depth, which can be up to tree height.

💡 For a tree with 20 nodes, this means roughly 20 function calls and 20 visits, which is manageable but can be slow for very deep trees.

Interview Verdict: Accepted but can cause stack overflow on very deep trees

This approach works but is not ideal for very large or skewed trees due to recursion depth limits.

🧠

Better (DFS with Early Stopping)

💡 This approach improves on brute force by stopping recursion early when a leaf is found, avoiding unnecessary exploration of deeper paths.

Intuition

Use DFS to explore paths, but prune branches once a leaf is found and track the minimum depth found so far to avoid exploring longer paths.

Algorithm

1. Initialize a variable to track minimum depth as infinity.
2. Perform DFS traversal, passing current depth.
3. When a leaf is found, update minimum depth if current depth is smaller.
4. Prune recursion if current depth exceeds minimum depth found.
5. Return the minimum depth after traversal.

💡 Pruning is the key optimization here, which can be subtle to implement correctly.

</>

Code

import math
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root):
    min_depth = math.inf
    def dfs(node, depth):
        nonlocal min_depth
        if not node:
            return
        if not node.left and not node.right:
            min_depth = min(min_depth, depth)
            return
        if depth >= min_depth:
            return
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    dfs(root, 1)
    return 0 if min_depth == math.inf else min_depth

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(minDepth(root))  # Output: 2

Line Notes

min_depth = math.infInitialize minimum depth to a very large number to track best found

def dfs(node, depth):Helper function to traverse tree with current depth parameter

if not node.left and not node.right:Leaf node found, update minimum depth if current path is shorter

if depth >= min_depth:Prune recursion if current path is already longer than best found

import java.util.*;
public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    private int minDepthVal = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 1);
        return minDepthVal;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            minDepthVal = Math.min(minDepthVal, depth);
            return;
        }
        if (depth >= minDepthVal) return;
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.minDepth(root)); // Output: 2
    }
}

Line Notes

private int minDepthVal = Integer.MAX_VALUE;Track minimum depth found so far initialized to max

if (node.left == null && node.right == null)Leaf node base case to update minimum depth

if (depth >= minDepthVal) return;Prune deeper paths that cannot improve the result

dfs(node.left, depth + 1);Recurse left subtree with incremented depth

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int minDepthVal = INT_MAX;

void dfs(TreeNode* node, int depth) {
    if (!node) return;
    if (!node->left && !node->right) {
        minDepthVal = min(minDepthVal, depth);
        return;
    }
    if (depth >= minDepthVal) return;
    dfs(node->left, depth + 1);
    dfs(node->right, depth + 1);
}

int minDepth(TreeNode* root) {
    if (!root) return 0;
    minDepthVal = INT_MAX;
    dfs(root, 1);
    return minDepthVal;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << minDepth(root) << endl; // Output: 2
    return 0;
}

Line Notes

int minDepthVal = INT_MAX;Global variable to track minimum depth initialized to max

if (!node->left && !node->right)Leaf node found, update minimum depth

if (depth >= minDepthVal) return;Prune recursion if current depth is not better than best

dfs(node->left, depth + 1);Recurse left subtree with incremented depth

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function minDepth(root) {
    let minDepthVal = Infinity;
    function dfs(node, depth) {
        if (!node) return;
        if (!node.left && !node.right) {
            minDepthVal = Math.min(minDepthVal, depth);
            return;
        }
        if (depth >= minDepthVal) return;
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    dfs(root, 1);
    return minDepthVal === Infinity ? 0 : minDepthVal;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(minDepth(root)); // Output: 2

Line Notes

let minDepthVal = Infinity;Initialize minimum depth to a large number to track best found

if (!node.left && !node.right)Leaf node base case to update minimum depth

if (depth >= minDepthVal) return;Prune recursion to avoid unnecessary deeper calls

dfs(node.left, depth + 1);Recurse left subtree with incremented depth

⏱

Complexity

TimeO(n) in worst case, better on average due to pruning

SpaceO(h) recursion stack, where h is tree height

Pruning reduces unnecessary exploration, but worst case still visits all nodes.

💡 For a balanced tree with 20 nodes, pruning can save many calls, speeding up the search.

Interview Verdict: Accepted and more efficient than brute force in practice

This approach is a good improvement but still uses recursion and can be replaced by BFS for guaranteed shortest path.

🧠

Optimal (Breadth-First Search - BFS)

💡 BFS naturally finds the shortest path in an unweighted tree by exploring level by level. This approach guarantees the minimum depth without exploring unnecessary nodes.

Intuition

Traverse the tree level by level using a queue. The first leaf node encountered during BFS traversal gives the minimum depth.

Algorithm

1. If the root is null, return 0.
2. Initialize a queue and add the root node with depth 1.
3. While the queue is not empty, dequeue the front node and its depth.
4. If the node is a leaf, return its depth immediately.
5. Otherwise, enqueue its non-null children with depth + 1.

💡 The key is stopping as soon as the first leaf is found, which BFS guarantees is the minimum depth.

</>

Code

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(minDepth(root))  # Output: 2

Line Notes

if not root:Handle empty tree case by returning 0

queue = deque([(root, 1)])Initialize queue with root node and depth 1

node, depth = queue.popleft()Process nodes level by level in FIFO order

if not node.left and not node.right:First leaf found, return its depth immediately for minimum

import java.util.*;
public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1));
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> current = queue.poll();
            TreeNode node = current.getKey();
            int depth = current.getValue();
            if (node.left == null && node.right == null) return depth;
            if (node.left != null) queue.offer(new Pair<>(node.left, depth + 1));
            if (node.right != null) queue.offer(new Pair<>(node.right, depth + 1));
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.minDepth(root)); // Output: 2
    }
}

Line Notes

if (root == null) return 0;Empty tree base case returns 0

Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();Queue stores nodes paired with their depth

Pair<TreeNode, Integer> current = queue.poll();Dequeue node and its depth for processing

if (node.left == null && node.right == null) return depth;Return depth immediately when first leaf found

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 1});
    while (!q.empty()) {
        auto [node, depth] = q.front();
        q.pop();
        if (!node->left && !node->right) return depth;
        if (node->left) q.push({node->left, depth + 1});
        if (node->right) q.push({node->right, depth + 1});
    }
    return 0;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << minDepth(root) << endl; // Output: 2
    return 0;
}

Line Notes

if (!root) return 0;Handle empty tree by returning 0

queue<pair<TreeNode*, int>> q;Queue holds nodes paired with their depth

auto [node, depth] = q.front();Dequeue node and depth for processing

if (!node->left && !node->right) return depth;Return depth immediately when first leaf found

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function minDepth(root) {
    if (!root) return 0;
    const queue = [[root, 1]];
    while (queue.length > 0) {
        const [node, depth] = queue.shift();
        if (!node.left && !node.right) return depth;
        if (node.left) queue.push([node.left, depth + 1]);
        if (node.right) queue.push([node.right, depth + 1]);
    }
    return 0;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(minDepth(root)); // Output: 2

Line Notes

if (!root) return 0;Empty tree base case returns 0

const queue = [[root, 1]];Initialize queue with root node and depth 1

const [node, depth] = queue.shift();Dequeue node and depth for processing

if (!node.left && !node.right) return depth;Return depth immediately when first leaf found

⏱

Complexity

TimeO(n)

SpaceO(n) for queue in worst case

Each node is visited once. BFS stops early at first leaf, so often faster than DFS in practice.

💡 For a tree with 20 nodes, BFS visits nodes level by level and stops as soon as it finds a leaf, minimizing work.

Interview Verdict: Accepted and optimal for this problem

BFS is the best approach here because it guarantees the shortest path to a leaf with minimal overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, coding the BFS approach is best because it is optimal, intuitive, and handles edge cases cleanly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(h) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Better (DFS with Early Stopping)	O(n) worst case, better average	O(h) recursion stack	Yes (deep recursion)	N/A	Good to mention as optimization
3. Optimal (BFS)	O(n)	O(n) queue	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, followed by optimizations, and finally the optimal BFS solution.

How to Present

Clarify the definition of minimum depth and leaf nodes.Describe the brute force recursive approach and its limitations.Explain how pruning improves DFS.Present BFS as the optimal solution and why it works.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer checks if you understand tree traversal, handle edge cases like one-child nodes, and choose the right algorithm for shortest path in trees.

Common Follow-ups

• What if the tree is very deep? → Use BFS to avoid stack overflow.
• Can you solve it iteratively? → BFS is iterative and preferred.
• How to handle trees with only one child nodes? → Carefully check null children in recursion.
• What if nodes have parent pointers? → BFS still applies, but can explore upwards.

💡 These follow-ups test your understanding of tree structure, recursion limits, and iterative solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves shortest path or minimum distance in a tree. 2) Tree nodes have children pointers. 3) Need to find nearest leaf or node satisfying condition. 4) BFS or level order traversal is a natural fit.

Signature Phrases

minimum depthshortest path to leafnearest leaf nodelevel by level traversal

NOT This Pattern When

Problems asking for maximum depth, diameter, or subtree sums are different patterns.

Similar Problems

Maximum Depth of Binary Tree - similar but asks for longest pathBalanced Binary Tree - uses depth calculations to check balancePath Sum - uses tree traversal to find paths with given sum

Practice

1. You are given a binary tree and need to output the nodes grouped by their vertical columns, from leftmost column to rightmost, preserving the top-to-bottom order within each column. Which approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) collecting nodes by column and sorting them by row and value afterwards

B. Greedy traversal picking nodes with minimum column index first without sorting or queue

C. Dynamic programming to compute vertical sums and then reconstruct node order

D. Breadth-first search (BFS) with column tracking using an ordered map to maintain column order and insertion order for nodes

Solution

1. Step 1: Understand problem requirements

   The problem requires grouping nodes by vertical columns and preserving top-to-bottom order within each column.

2. Step 2: Evaluate approaches

   DFS with sorting (A) works but is less efficient; greedy (B) fails to preserve order; DP (D) is unrelated. BFS with column tracking and ordered map (C) naturally preserves order and column sorting efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS with ordered map preserves vertical order and top-to-bottom traversal [OK]

Hint: BFS with ordered map preserves vertical and top-down order [OK]

Common Mistakes:

• Assuming DFS alone preserves top-to-bottom order without sorting
• Using greedy approach ignoring node order within columns

2. You need to find the maximum value at each depth level of a binary tree. Which approach guarantees an efficient and correct solution for this problem?

easy

A. Perform a breadth-first search (BFS) level order traversal, tracking the maximum value per level.

B. Use a greedy traversal that picks the largest child node at each step without level tracking.

C. Apply a dynamic programming approach that stores maximum values for subtrees without level information.

D. Use a depth-first search (DFS) without tracking levels, updating a global maximum value.

Solution

1. Step 1: Understand the problem requires per-level maximums

   The problem asks for the largest value at each tree row (level), so we must process nodes grouped by their depth.

2. Step 2: Identify BFS level order traversal as the correct pattern

   BFS naturally processes nodes level by level, allowing us to track and update the maximum value for each level efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS processes nodes level-wise, perfect for per-level max tracking [OK]

Hint: Level order traversal matches per-level processing [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy picks largest child but misses other nodes at same level
• DP without level info cannot isolate per-level max

3. Identify the bug in the following code snippet that attempts to find the bottom-left tree value using BFS:

from collections import deque

class Solution:
    def findBottomLeftValue(self, root):
        queue = deque([root])
        node = None
        while queue:
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return node.val

What is the bug in this code?

medium

A. Appending left child before right child causes the last node to be the bottom-right, not bottom-left.

B. Not initializing node before the loop causes a runtime error if root is None.

C. Returning node.val instead of queue[-1].val returns the wrong node value.

D. Using deque instead of list causes inefficient queue operations.

Solution

1. Step 1: Analyze enqueue order

   The code enqueues left child before right child, so BFS processes nodes left to right at each level.

2. Step 2: Identify last node popped

   Because left child is enqueued first, the last node popped is the bottom-right node, not bottom-left.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Right-to-left insertion is needed to get bottom-left node last [OK]

Hint: Order of child insertion in BFS affects which node is last popped [OK]

Common Mistakes:

• Assuming left-first enqueue gives bottom-left node
• Confusing last popped node with first node at last level
• Thinking deque is inefficient for BFS

4. The following code attempts to connect next right pointers in any binary tree. Identify the line containing the subtle bug that causes incorrect next pointer connections for nodes with only one child.

def connect(root):
    if not root:
        return null

    if root.left and root.right:
        root.left.next = root.right

    next_node = root.next
    while next_node:
        if next_node.left:
            next_child = next_node.left
            break
        if next_node.right:
            next_child = next_node.right
            break
        next_node = next_node.next
    else:
        next_child = null

    if root.right:
        root.right.next = next_child
    if root.left:
        root.left.next = next_child

    connect(root.right)
    connect(root.left)

    return root

medium

A. Line: if root.left: root.left.next = next_child

B. Line: if root.right: root.right.next = next_child

C. Line: if root.left and root.right: root.left.next = root.right

D. Line: connect(root.right)

Solution

1. Step 1: Analyze next pointer assignments

   When both children exist, left.next -> right is set correctly. For single child cases, next_child is found from root.next chain.

2. Step 2: Identify bug in single child handling

   Both if root.right and if root.left set their next to next_child unconditionally. This causes left child to overwrite its next pointer even if right child exists, breaking correct connections.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing if root.left to elif root.left fixes the bug [OK]

Hint: Use elif to avoid overwriting next pointers for left child [OK]

Common Mistakes:

• Setting both left and right child's next unconditionally
• Not breaking after setting left.next when right child exists
• Misordering recursive calls

5. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes