Maximum Depth of Binary Tree

time: O(n)
space: O(h)
tags: trees · recursion · dfs

in the wild Computing a robot's kinematic chain depth (URDF leaf-to-root walk), or the max nesting depth of a JSON/DOM document.

Problem

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to the farthest leaf. An empty tree has depth 0.

Examples

      3
     / \           depth = 3
    9  20          (path: 3 → 20 → 7)
       / \
      15  7

   1
    \              depth = 2
     2

   (empty)         depth = 0

Why this is the canonical first tree problem

Two lines of code, but it teaches you to think in trees:

depth(node) = 0                                  if node is null
            = 1 + max(depth(left), depth(right))  otherwise

That's the recursive structure of a tree in one equation. The base case (null subtree) returns 0. The recursive case asks each child for its own depth — trusting recursion to handle subtrees — then combines: take the deeper child, add one for the current node.

Every tree problem worth solving has this shape: define what the answer is at a single node in terms of the answers from its children. Get that recurrence right and the code writes itself. This is also why a "max-depth" question is the warm-up to every tree interview — interviewers want to see whether you naturally reach for the recursive decomposition.

Hints

Hint 1 — base case

What's the depth of an empty tree (a null node)? The cleanest convention says 0 — there's no node, so no levels.

Hint 2 — recursive case

If a node has children, how does its depth relate to its children's depths? The answer should let you express depth(node) purely in terms of depth(left) and depth(right) plus a constant.

Hint 3 — iterative alternative

If you'd rather not use recursion (e.g. fear of stack overflow on a 100k-deep linked-list-like tree), you can do level-order BFS with a queue and count the levels you process. Same O(n) time but O(w) space (widest level) instead of O(h).

Solution

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def max_depth(root: Optional[Node]) -> int:
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Build the trees from the examples.
t1 = Node(3, Node(9), Node(20, Node(15), Node(7)))
t2 = Node(1, None, Node(2))
t3 = None
cases = [(t1, 3), (t2, 2), (t3, 0)]
for root, expected in cases:
    got  = max_depth(root)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} max_depth(...) = {got}  (expected {expected})")

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

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

const t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
const t2 = new Node(1, null, new Node(2));
const t3 = null;
const cases = [[t1, 3], [t2, 2], [t3, 0]];
for (const [root, expected] of cases) {
  const got = maxDepth(root);
  console.log(`${got === expected ? "✓" : "✗"} maxDepth(...) = ${got}  (expected ${expected})`);
}

// Box-based tree — owns its children outright.
pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

pub fn max_depth(root: &Option<Box<Node>>) -> i32 {
    match root {
        None    => 0,
        Some(n) => 1 + max_depth(&n.left).max(max_depth(&n.right)),
    }
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let t1 = node(3, leaf(9), node(20, leaf(15), leaf(7)));
    let t2 = node(1, None, leaf(2));
    let t3: Option<Box<Node>> = None;
    let cases = [(&t1, 3), (&t2, 2), (&t3, 0)];
    for (root, expected) in cases {
        let got  = max_depth(root);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} max_depth(...) = {}  (expected {})", got, expected);
    }
}

#include <algorithm>
#include <iostream>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

int max_depth(Node* root) {
    if (!root) return 0;
    return 1 + std::max(max_depth(root->left), max_depth(root->right));
}

int main() {
    // Trees leak; fine for a 50-line demo.
    Node* t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
    Node* t2 = new Node(1, nullptr, new Node(2));
    Node* t3 = nullptr;
    std::pair<Node*, int> cases[] = { {t1, 3}, {t2, 2}, {t3, 0} };
    for (auto& [root, expected] : cases) {
        int got = max_depth(root);
        std::cout << (got == expected ? "✓" : "✗")
                  << " max_depth(...) = " << got
                  << "  (expected " << expected << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

static int imax(int a, int b) { return a > b ? a : b; }

int max_depth(Node* root) {
    if (!root) return 0;
    return 1 + imax(max_depth(root->left), max_depth(root->right));
}

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* t1 = mk(3, mk(9, NULL, NULL), mk(20, mk(15, NULL, NULL), mk(7, NULL, NULL)));
    Node* t2 = mk(1, NULL, mk(2, NULL, NULL));
    Node* t3 = NULL;
    printf("%s max_depth(t1) = %d  (expected 3)\n", max_depth(t1) == 3 ? "✓" : "✗", max_depth(t1));
    printf("%s max_depth(t2) = %d  (expected 2)\n", max_depth(t2) == 2 ? "✓" : "✗", max_depth(t2));
    printf("%s max_depth(t3) = %d  (expected 0)\n", max_depth(t3) == 0 ? "✓" : "✗", max_depth(t3));
    return 0;
}

idle

The Python and JS versions are five lines; Rust spends extra ceremony only to honor ownership. The pattern is identical across all five: null-tree base case, recurse into both children, combine.

Complexity

Time: O(n) — every node is visited exactly once.
Space (recursive): O(h) where h is the tree height — that's the call-stack depth at the deepest moment. For a balanced tree h = log n; for a degenerate (linked-list-shaped) tree h = n.
Space (iterative BFS): O(w) where w is the widest level. A perfectly balanced binary tree has w = n/2 at the bottom — recursion is usually more space-efficient on balanced trees.

In the wild

URDF kinematic depth. A robot's URDF tree is rooted at the base link; the maximum depth from base to any end-effector is what max_depth measures.
JSON / DOM nesting. Linter / formatter tools measure max nesting depth to flag pathological documents.
Compiler AST analysis. Static-analysis passes often need the AST depth to bound recursion budget on the next pass.
Filesystem max path depth. find . -type d | awk -F/ '{print NF}' | sort -n | tail -1 is "max-depth" in shell.

Variations

Minimum depth. Tricky — a node with one missing child must use the non-null child's depth, not the smaller 0. Off-by-one trap.
Diameter. Diameter of Binary Tree — longest path between any two nodes. Same recursion shape, but tracks left+right at every node.
Balanced check. Walk + return both the depth and a balanced flag in one pass.
All paths. Enumerate every root-to-leaf path. Backtrack with a path stack.