The O(n) Club: Maximum Depth of Binary Tree: Because Shallow Isn’t Cool

The O(n) Club: Maximum Depth of Binary Tree — Because Shallow Isn’t Cool

⚡ TL;DR

Measure how far you can plummet from root to leaf in a binary tree. Just let recursion do all the panic-walking for you—visit both kids, take the bigger depth, and add one for your rung on the family tree. Java time:

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

🧠 How Devs Usually Mess This Up

Is the depth about nodes or edges? Spoiler: LeetCode says it’s nodes. Give the recruiter an answer off by one, and watch them smile politely (while mentally moving your resume to the bin). Don’t call non-leaf nodes “leaves” just because they look lonely—only nodes with zero kids count.

Also, depth one means just the root, not zero. Sorry, textbook sticklers: edge-counters go home.

🔍 What’s Actually Going On

Imagine the world’s worst elevator: at every floor (node), you can only ride left or right, and eventually you hit a dead-end penthouse (leaf). The maximum depth is the longest wild ride from lobby (root) to roof (leaf).

In code: for each node, say “what’s deeper, left or right?” Tack on a +1 for each step, until you tumble off the tree’s edge. No hidden trapdoors, just classic recursion, DFS-style.

🛠️ PseudoCode

• If the node is null, return 0.
  // Ghost node: it's time to stop.
• Otherwise:
  • Ask left kid for their max depth (recursively).
  • Ask right kid for theirs.
  • Keep whichever result is bigger (Math.max!), then add 1 for yourself.
  // DeepestPath = Math.max(left, right) + 1
• Return that result upward like an ambitious ladder climber.

💻 The Code

// Binary tree node, in basic Java:
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Node vs edge debate—flunked interviews are built on this.
• Super-skewed trees (single branches): enjoy your StackOverflowError—go iterative or BFS if you’re feeling unlucky.
• Empty tree? Return 0, not 1.
• Time: O(n), space: O(h) for recursive call stack (that’s height h, up to n if your tree looks suspiciously like a linked list).

🧠 Interviewer Brain-Tattoo

Recursion: when you call yourself so much you might reach therapy-level depth. But hey, that’s the job.