Module 17 · Binary Trees: Recursive DFS and Structural Contracts

162. Maximum Depth

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the maximum depth of a finite binary tree, measured in nodes on a root-to-leaf path. An empty tree has depth zero; a single node has depth one. Nodes may have any integer values, which do not affect the answer. Do not mutate the tree.

Examples

Example 1

max_depth(build_tree([1,2,3,4]))
=> 3

The longest path is 1,2,4 and contains three nodes.

Example 2

max_depth(None)
=> 0

No nodes contribute to depth.

Example 3

max_depth(build_tree([9]))
=> 1

A singleton has node-count depth one.

Reveal the worked solution and reasoning

Why this mechanism works

A helper should return one complete fact about its subtree. If a node has no subtree, its depth is zero. Otherwise a longest path takes the current node and then whichever child offers the larger depth. This is a postorder computation even though the code is a compact expression.

State and boundaries

max_depth(node) returns the exact node-count height of node's subtree; child calls are independent results.

Protocol

Return zero for None.
Obtain left and right subtree depths.
Return one plus their maximum.

Visualization

       1                 depth 3
      / \
     2   3               child depths 2 and 1
    /
   4                     leaf depth 1

Python implementation

from structures import build_tree

def max_depth(root):
    if root is None:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return 1 + max(left, right)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

max_depth(build_tree([1,2,3,4]))

L4 max_depth: if root is None:
root=N1(val=1,left=N2,right=N3)

L4 max_depth: if root is None:
root=N2(val=2,left=N4,right=None)

L4 max_depth: if root is None:
root=N4(val=4,left=None,right=None)

L4 max_depth: if root is None:
root=None

L6 max_depth: left = max_depth(root.left)
root=N4(val=4,left=None,right=None); left=0

L4 max_depth: if root is None:
root=None

L7 max_depth: right = max_depth(root.right)
root=N4(val=4,left=None,right=None); left=0; right=0

L6 max_depth: left = max_depth(root.left)
root=N2(val=2,left=N4,right=None); left=1

... 5 intermediate state changes omitted ...

L6 max_depth: left = max_depth(root.left)
root=N3(val=3,left=None,right=None); left=0

L4 max_depth: if root is None:
root=None

L7 max_depth: right = max_depth(root.right)
root=N3(val=3,left=None,right=None); left=0; right=0

L7 max_depth: right = max_depth(root.right)
root=N1(val=1,left=N2,right=N3); left=2; right=1

Result: 3. The longest path is 1,2,4 and contains three nodes.

max_depth(None)

L4 max_depth: if root is None:
root=None

Result: 0. No nodes contribute to depth.

Why the solution is correct

The empty-tree base matches the definition. Every nonempty root-to-leaf path uses the root and one child path. Choosing the larger correct child depth therefore yields exactly the longest such path. Structural induction proves every return value; finite child subtrees ensure termination.

Time and space

O(n) time and O(h) recursive stack space for n nodes and tree height h. A skewed tree can have h=n and exceed Python's recursion limit.

Common mistakes

Returning zero for a leaf changes the unit to edges. Using the sum of child depths measures neither depth nor a valid single downward path.

Reasoning card

State: max_depth(node) returns the exact node-count height of node's subtree; child calls are independent results.

Invariant: Each call returns the correct depth of its subtree.

Decision to rehearse: Children return subtree depths upward.

Finish: Return one plus their maximum

Transfer exercise

Compute the same result with an explicit stack carrying (node,depth), avoiding recursion depth limits.