The O(n) Club: Minimum Depth of Binary Tree – Stop Calling Null a Leaf

The O(n) Club: Minimum Depth of Binary Tree – Stop Calling Null a Leaf

⚡ TL;DR

Shortest path from root to an actual leaf (not a lonely child node)? Don’t hypnotize yourself with nulls. BFS bails fast; DFS is nice until your stack explodes. Here’s a Java taste:

// DFS version—fast, but mind the recursion stack!
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null) return 1 + minDepth(root.right);
    if (root.right == null) return 1 + minDepth(root.left);
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

🧠 How Devs Usually Mess This Up

Everyone’s favorite mistake? Treating a node that’s missing ONE child as if it’s earned ‘leaf’ status. (It hasn’t. It’s like calling yourself a senior dev after your first merge.) Also, plenty of folks keep hiking down every trail in the tree—even after hitting the first leaf. Enjoy O(n) for fun, but why?

🔍 What’s Actually Going On

Imagine your file system. You want the shortest path from C:\ to any file, not the one that’s four subfolders deep. A real leaf means no children. DFS will find the answer, but might also find stack overflow if your tree’s a spaghetti strand. BFS is like a treasure hunter—first shiny leaf, done, let’s hit the coffee shop.

🛠️ PseudoCode

• If tree is empty (root == null):
  return 0;
  No tree, no depth, no drama.
• If only left or right exists:
  return 1 + minDepth(child);
  Keep crawling down the non-null branch—don’t pretend null is a leaf.
• If both sides exist:
  return 1 + min(minDepth(left), minDepth(right));
  Whether you’re a DFS or BFS stan, pick the quicker path.
• For BFS: Queue node-depth pairs, level-by-level, first leaf you see—return depth and drop mic.

• Remember: Only terminal nodes are leaves. ‘Null’ is just an empty seat at the dinner table.

💻 The Code

// Java BFS approach—stacks stay chill
import java.util.*;
 class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class MinDepthBinaryTree {
    static class NodeDepth {
        TreeNode node;
        int depth;
        NodeDepth(TreeNode n, int d) { node = n; depth = d; }
    }
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue
<nodedepth> q = new LinkedList<>();
        q.offer(new NodeDepth(root, 1));
        while (!q.isEmpty()) {
            NodeDepth nd = q.poll();
            TreeNode node = nd.node;
            int depth = nd.depth;
            if (node.left == null && node.right == null) return depth;
            if (node.left != null) q.offer(new NodeDepth(node.left, depth + 1));
            if (node.right != null) q.offer(new NodeDepth(node.right, depth + 1));
        }
        return 0; // Only possible if root is null
    }
}
</nodedepth>

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t treat null children as leaves. Seriously. Interviewers know.
• Empty tree? Answer is zero. Not negative zero. Not NULL. Just…zero.
• Got one branch only? You must keep walking—there’s no shortcut down the abyss.
• BFS zips out fast for wide trees; DFS turns into a memory drama queen for tall ones.
• Both algorithms run O(n), but space can balloon for BFS on wide trees and for DFS on deep ones. No extra points for pancake-stack crashes.

🧠 Interviewer Brain-Tattoo

“A missing child isn’t a leaf; it’s just your code looking for an excuse to be wrong.”