🧑‍💻 Interviewer Guide: Minimum Depth of Binary Tree (UMPIRE Method)

https://leetcode.com/problems/minimum-depth-of-binary-tree/

📌 Problem Statement

Given the root of a binary tree, Return 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.

---

🧭 U — Understand the Problem

Interviewer Prompts & Possible Answers:

• "Can you restate the problem in your own words?" → "We want to find the shortest path from the root to a leaf node, measured in number of nodes."

• "What qualifies as a 'leaf node'?" → "A node with no left or right children."

• "What should we return if the tree is empty?" → "We should return 0."

• "What if the tree has only one node?" → "The minimum depth is 1."

• "Are we counting edges or nodes?" → "We're counting nodes along the shortest path to a leaf."

• "What’s the difference between this and maximum depth?" → "This asks for the shortest root-to-leaf path, while maximum depth asks for the longest."

---

🧪 M — Match with Patterns

Interviewer Prompts & Possible Answers:

• "What category of problems does this fall into?" → "Tree traversal, similar to level order or DFS problems."

• "What traversal method might be most efficient?" → "Breadth-first search (BFS) can find the minimum depth faster since it finds the first leaf node."

• "Could this be solved with depth-first search?" → "Yes, but we have to be careful not to count paths that don't reach a leaf."

• "What makes this problem tricky?" → "Handling nodes with only one child. We must make sure we don’t treat those as leaves."

• "What real-world analogy can help?" → "It’s like finding the closest exit in a building—you want the first complete path, not just any branch."

---

🛠️ P — Plan the Solution

Interviewer Prompts & Possible Answers:

• "Can you outline the BFS approach?" → "Use a queue. Add the root with depth 1. For each node, if it's a leaf, return depth. Otherwise, enqueue its children with depth+1."

• "How does this ensure we find the minimum?" → "BFS explores nodes level by level. The first leaf found is on the shortest path."

• "What about a DFS approach?" → "Recurse down both left and right children. If one child is null, only consider the non-null child. Return 1 + min of left/right depth."

• "Why not just use min(left, right)?" → "Because if one side is null, min(0, depth) gives incorrect results. We must ignore the null side."

---

⌨️ I — Implement

BFS (Queue-Based, Early Exit on First Leaf)

from collections import deque

def minDepth(root):
    if not root:
        return 0
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # Check for leaf
        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))

DFS (Recursive, Handle Null Children Carefully)

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

---

🔁 R — Review

Interviewer Prompts & Possible Answers:

• "What edge cases should we consider?" → "Empty tree, single-node tree, skewed trees with only one child per node."

• "How would you explain the BFS vs DFS behavior?" → "BFS finds the shallowest leaf first and exits early. DFS explores full paths and picks the shortest afterward."

• "Why is it important to handle null children carefully in DFS?" → "Because a node with only one child is not a leaf; counting both sides as zero gives wrong results."

• "How would you test your solution?" → "Construct small trees with known minimum depths and check edge cases."

Test Cases:

def test_minDepth():
    assert minDepth(None) == 0  # Empty tree
    
    root = TreeNode(1)
    assert minDepth(root) == 1  # Single node
    
    root = TreeNode(1, TreeNode(2))
    assert minDepth(root) == 2  # Left child only
    
    root = TreeNode(1, None, TreeNode(2))
    assert minDepth(root) == 2  # Right child only
    
    root = TreeNode(1,
        left=TreeNode(2, TreeNode(4)),
        right=TreeNode(3)
    )
    assert minDepth(root) == 2  # Right path is shallower
    
    root = TreeNode(1,
        left=TreeNode(2, TreeNode(4, TreeNode(5))),
        right=TreeNode(3, None, TreeNode(6))
    )
    assert minDepth(root) == 3  # Path: 1 -> 3 -> 6

---

🧹 E — Evaluate & Optimize

Interviewer Prompts & Possible Answers:

• "What’s the time and space complexity of BFS?" → "Time: O(n) in the worst case if tree is balanced. Space: O(w), where w is the max width of the tree (queue size)."

• "What about the DFS approach?" → "Time: O(n), must explore every node. Space: O(h) for the call stack, where h is the tree height."

• "Which is more efficient in practice?" → "BFS can be faster since it returns as soon as it finds a leaf."

• "Can this be solved iteratively without a queue?" → "It’s possible but less intuitive—BFS naturally maps to queue use."

• "How would this perform on an unbalanced tree?" → "DFS might go deep before finding a short path. BFS avoids that by exploring level by level."

• "When would you prefer DFS?" → "If memory is tight and the tree is very shallow, DFS might be better."