111. Minimum Depth of Binary Tree

Tree Depth-First Search Binary Tree Breadth-First Search

Time: O(n)

Space: O(h)

Intuition

Minimum depth is the depth to the nearest leaf. BFS stops at the first leaf encountered - that level is the minimum depth. This avoids exploring the entire tree (DFS would need to).

Algorithm

1If root is null, return 0.
2BFS with a queue, tracking depth.
3For each node: if both children are null (leaf), return current depth.
4Enqueue non-null children.

Example Walkthrough

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

1.Level 1: node 2 has only right child - not a leaf. Level 2: node 3 - not a leaf. ... Level 5: node 6 - leaf. Return 5.

Output: 5

Common Pitfalls

•A node with only one child is NOT a leaf - do not return early there.
•DFS approach: min(left, right) + 1 fails when one child is null. Must handle: if left == null return right+1 (and vice versa).

111.cs

// Approach: DFS recursion. A node with one null child is not a leaf, so
// recurse only on the non-null side in that case.
// Time: O(n) Space: O(h)

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

public class Solution
{
    public int MinDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        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;
    }
}

Was this solution helpful?