Max Depth¶

Problem¶

Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to a leaf).

Approach¶

DFS recursive: depth = 1 + max(depth(left), depth(right)). Base case: empty tree has depth 0.

When to Use¶

Recursive tree measurement — "max depth", "height", "diameter", any metric that aggregates over subtrees with a simple recurrence. Foundation for balanced-tree checks and tree diameter computation.

Complexity¶


Time	`O(n)`
Space	`O(h) where h = height of tree (call stack)`

Implementation¶

SolutionTestsChallenge

max_depth ¶

Maximum depth of a binary tree.

Problem

Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to a leaf).

Approach

DFS recursive: depth = 1 + max(depth(left), depth(right)). Base case: empty tree has depth 0.

When to use

Recursive tree measurement — "max depth", "height", "diameter", any metric that aggregates over subtrees with a simple recurrence. Foundation for balanced-tree checks and tree diameter computation.

Complexity

Time: O(n) Space: O(h) where h = height of tree (call stack)

max_depth ¶

max_depth(root: TreeNode | None) -> int

Return the maximum depth of a binary tree.

max_depth(TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None))) 3

Source code in src/algo/trees/max_depth.py

def max_depth(root: TreeNode | None) -> int:
    """Return the maximum depth of a binary tree.

    >>> max_depth(TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None)))
    3
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

tests/trees/test_max_depth.py

"""Tests for maximum depth of binary tree."""

from algo.trees.max_depth import TreeNode, max_depth


class TestMaxDepth:
    def test_balanced_tree(self) -> None:
        tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
        assert max_depth(tree) == 3

    def test_empty_tree(self) -> None:
        assert max_depth(None) == 0

    def test_single_node(self) -> None:
        assert max_depth(TreeNode(1)) == 1

    def test_left_skewed(self) -> None:
        tree = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
        assert max_depth(tree) == 4

    def test_right_skewed(self) -> None:
        tree = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
        assert max_depth(tree) == 3

    def test_asymmetric(self) -> None:
        tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
        assert max_depth(tree) == 3

Implement it yourself

Run: just challenge trees max_depth

Then implement the functions to make all tests pass. Use just study trees for watch mode.

Reveal Solution

max_depth ¶

Maximum depth of a binary tree.

Problem

Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to a leaf).

Approach

DFS recursive: depth = 1 + max(depth(left), depth(right)). Base case: empty tree has depth 0.

When to use

Recursive tree measurement — "max depth", "height", "diameter", any metric that aggregates over subtrees with a simple recurrence. Foundation for balanced-tree checks and tree diameter computation.

Complexity

Time: O(n) Space: O(h) where h = height of tree (call stack)

max_depth ¶

max_depth(root: TreeNode | None) -> int

Return the maximum depth of a binary tree.

max_depth(TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None))) 3

Source code in src/algo/trees/max_depth.py

def max_depth(root: TreeNode | None) -> int:
    """Return the maximum depth of a binary tree.

    >>> max_depth(TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None)))
    3
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))