Maximum Depth of Binary Tree

Recursive DFS

1 + max(left_depth, right_depth). This IS the recursive template.

Published Apr 16, 2026

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.

Input

root = [3, 9, 20, null, null, 15, 7]

Output

Explanation

Path 3 → 20 → 15 (or 3 → 20 → 7) has 3 nodes.

Input

root = [1, null, 2]

Output

Intuition

Depth at a node is one more than the deeper of its two children's depths. The base case is the empty subtree, whose depth is 0.

That sentence is the entire algorithm. It's the canonical "answer-from-children" recurrence — the one to internalize before any harder tree problem, because diameter, path-sum, and balanced-check are all variations on the same shape.

The iterative version reframes it: instead of asking "how deep am I?", you walk the tree level by level and count how many levels you traverse. Same number, different traversal order.

Approach

Recursive DFS

TimeO(n)

SpaceO(h)

Recommended

Return 1 + max(maxDepth(left), maxDepth(right)). The recursion bottoms out at null, which contributes 0.

h is the tree's height — O(log n) for balanced trees, O(n) for skewed.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let n = node.borrow();
                1 + Self::max_depth(n.left.clone()).max(Self::max_depth(n.right.clone()))
            }
        }
    }
}

Rust · runnable

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

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

TypeScript · runnable

Iterative BFS (level count)

TimeO(n)

SpaceO(w)

Push the root onto a queue, then peel one full level at a time. Each peel increments the depth counter. w is the maximum width — at worst O(n/2).

Choose this when you need to avoid recursion depth on adversarial skewed trees, or when you're already doing level-order work for an adjacent problem.

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
        if let Some(r) = root {
            queue.push_back(r);
        }
        let mut depth = 0;
        while !queue.is_empty() {
            depth += 1;
            for _ in 0..queue.len() {
                let node = queue.pop_front().unwrap();
                let n = node.borrow();
                if let Some(l) = &n.left {
                    queue.push_back(l.clone());
                }
                if let Some(r) = &n.right {
                    queue.push_back(r.clone());
                }
            }
        }
        depth
    }
}

Rust · runnable

function maxDepth(root: TreeNode | null): number {
  if (root === null) return 0;
  const queue: TreeNode[] = [root];
  let depth = 0;
  while (queue.length) {
    let levelSize = queue.length;
    while (levelSize-- > 0) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    depth++;
  }
  return depth;
}

TypeScript · runnable

Trace

Recursive evaluation on root = [3, 9, 20, null, null, 15, 7]:

call	left depth	right depth	returns
maxDepth(9)	0	0	1
maxDepth(15)	0	0	1
maxDepth(7)	0	0	1
maxDepth(20)	1	1	2
maxDepth(3)	1	2	3

The recursion bottoms out at the leaves, then max + 1 propagates back up.

Edge cases

Empty tree — both approaches return 0.
Single node — depth is 1.
Skewed (linked-list shaped) tree — recursive depth is O(n); the BFS version stays at O(1) queue size and O(n) time.

Takeaway

The "answer at this node = function of answers from children" template is the entire trees curriculum in one sentence. Master it on max-depth (return one number), then variations follow: diameter (return depth, track global max), path sum (carry an accumulator), balanced-check (return depth or sentinel for "unbalanced").

Easy#226

Invert Binary Tree

The simplest recursive tree transformation. Swap left and right, recurse.

Easy#543

Diameter of Binary Tree

Key insight: the answer might not pass through the root. Track a global max.

Hard#124

Binary Tree Maximum Path Sum

Like diameter but with values. Return one-side max to parent, track global two-side max.