Maximum Depth of Binary Tree

EASY✓ CHIP-TIMEDLC #104 — FULL STATEMENT ↗

The drill: Find how many nodes deep a binary tree goes — the longest chain of parent-to-child steps from the root down to any leaf, counted in levels.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to report how many levels deep it goes — the number of nodes along the longest path from the root down to whichever leaf sits furthest away.

Depth is counted in nodes visited, not edges crossed: a tree containing only the root has depth one, and each additional level down adds one more to that count.

An empty tree — no root at all — has a depth of zero, the base case every recursive or level-by-level approach has to bottom out at.

EX 01

root = []

→ 0

EMPTY TREE

EX 02

root = [1]

→ 1

SINGLE NODE

EX 03

root = [1, 2]

→ 2

ONE EXTRA LEVEL

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
depth counts nodes on the longest root-to-leaf path, an empty tree counts as depth zero

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Depth is a per-level question. What structure naturally processes a tree one full level at a time?

HINT 2 THE STRUCTURE

A queue holding one level's worth of nodes at a time counts levels directly — pop the whole current level, push its children, that's one level counted.

HINT 3 ONE STEP FROM THE ANSWER

Or skip the bookkeeping entirely: the depth of a tree is 1 plus the deeper of its two subtrees' depths. An empty tree has depth 0 — that's the whole recursion.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BOTTOM-UP DEPTHPATTERN · RECURSIVE DEPTHroot = [5, 3, 8, 1, 4, 7, 9]

STEP 1

Depth of a node is 1 plus the deeper of its two children's depths, bottoming out at 0 for an empty subtree. Start the recursion at the root, value 5.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/maximum-depth-of-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 5 LN

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        level = [root]
        while level:
            depth += 1
            nxt = []
            for node in level:
                if node.left:
                    nxt.append(node.left)
                if node.right:
                    nxt.append(node.right)
            level = nxt
        return depth

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 16 LN

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

TIME O(N)SPACE O(H)JAVA · RACE PACE · 8 LN

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        List<TreeNode> level = new ArrayList<>();
        level.add(root);
        while (!level.isEmpty()) {
            depth++;
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode node : level) {
                if (node.left != null) {
                    next.add(node.left);
                }
                if (node.right != null) {
                    next.add(node.right);
                }
            }
            level = next;
        }
        return depth;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED