Trees: The Core Idea

Your laptop's file browser shows that a folder called projects uses 4.2 GB. How did it know? It asked each subfolder for its size, added the sizes of the files sitting directly inside, and summed. Each subfolder did the same with its subfolders. No folder needed to understand the whole disk; each one only combined the answers of its children.

That is the entire pattern. The answer at a node is built from the answers at its children. Trees are the largest single category of coding-interview questions, and almost all of them are this one idea with a different "combine" step.

Unlike most patterns in this course, trees are not about replacing a slow brute force. The natural recursive solution already visits each node once, so it is already O(n). What goes wrong is correctness at the edges: an empty child, a very deep tree, a value that should have been recorded but was returned instead.

The words, and the node class

Every tree lesson in this section uses this class:

1from __future__ import annotations23from dataclasses import dataclass4from typing import Optional567@dataclass(eq=False)8class TreeNode:9    """One node of a binary tree."""10    val: int11    left: Optional[TreeNode] = None12    right: Optional[TreeNode] = None

eq=False keeps Python's default behaviour of comparing nodes by identity. Two different nodes that happen to hold the value 5 stay different, and nodes can still be put in sets and used as dictionary keys.

A note on counting. Some problems count depth in nodes (a single node has depth 1) and some in edges (a single node has height 0). Maximum Depth counts nodes; Diameter counts edges. Always check which one the problem wants before writing the base case.

How to recognise it

• The input is literally a tree. The signature takes a TreeNode. Half of tree problems announce themselves this way.
• The data is a hierarchy. Folders, an org chart, comment threads, an expression like (2 + 3) × 4. Anything where one item contains others.
• The definition refers to itself. "A tree is balanced if both subtrees are balanced and their heights differ by at most one." When the definition recurses, so does the code.
• Words about levels. "Level by level", "each row", "the shallowest leaf", "what you see from the right side". These point to breadth-first search.
• The constraints mention height. "The tree has up to 10⁵ nodes" with no promise of balance means a chain of 10⁵ nodes is possible. That is a warning about recursion depth, not about time.

The one-sentence test: can I answer this for a node if a helper hands me the answers for its two children? If yes, write that helper.

How it works

Why can't a simple loop solve tree problems? Try measuring the depth with one pointer:

1def max_depth_wrong(root: Optional[TreeNode]) -> int:2    """Only measures the leftmost path — wrong on most trees."""3    depth = 04    node = root5    while node:6        depth += 17        node = node.left8    return depth

On a tree whose left side is short and right side is long, this returns the wrong number and never notices. A tree branches, and one loop variable cannot be in two places at once. Recursion — or an explicit stack — exists to remember the branches you have not walked yet.

The recursion is correct for one reason, and it is worth saying plainly. Write down what the function returns for any subtree: "max_depth(node) returns the number of nodes on the longest path down from node". Then check two things:

1. The base case matches the sentence. For an empty subtree the longest path has 0 nodes, so return 0.
2. The combine step matches the sentence, assuming the children's answers are right. The longest path from node is node itself plus the longer of its children's paths: 1 + max(left, right).

If both hold, the function is correct for every tree, by induction on the height. You never trace the whole recursion in your head; you trust the sentence for the children and check one node.

Variants: the four ways to walk a tree

There is one depth-first walk, and three moments at which a node can do its own work:

1def traverse(node: Optional[TreeNode]) -> None:2    if node is None:3        return4    # (1) preorder: work before either child5    traverse(node.left)6    # (2) inorder: left subtree finished, right not started7    traverse(node.right)8    # (3) postorder: both subtrees finished

The fourth walk, breadth-first, uses a queue instead of recursion and visits the tree one level at a time.

Trace all four on this tree:

        1      /   \     2     3    / \   4   5

The first three are not three algorithms. The walk is identical — each node is reached from above, returned to after its left child, and returned to after its right child. The "order" only names which of those three visits does the work. That is why converting between them means moving one line.

There is a second choice, independent of order: which way the information flows.

Some problems need both, and some need a third thing: an answer that is neither passed down nor returned up, but recorded on the side in an outer variable. Diameter of Binary Tree is the lesson for that.

The templates

Template 1 — recursive DFS. Three steps, and the base case is the hard part.

1def solve(node: Optional[TreeNode]) -> int:2    """Say here, in one sentence, what this returns for the subtree at node."""3    if node is None:4        return IDENTITY                   # the answer for an empty subtree5    left = solve(node.left)               # trust the sentence for each child6    right = solve(node.right)7    return combine(node.val, left, right)

IDENTITY is whatever makes combine correct when a child is missing. For depth or size, 0. For "is valid", True. For a maximum over values, negative infinity; for a minimum, positive infinity. Choosing it wrong is the most common tree bug, because the code still runs.

Filled in for maximum depth:

1def max_depth(root: Optional[TreeNode]) -> int:2    """Number of nodes on the longest root-to-leaf path."""3    if root is None:4        return 0                          # an empty tree has no levels5    left = max_depth(root.left)6    right = max_depth(root.right)7    return 1 + max(left, right)           # this node sits one level above the deeper child

Calls return in postorder on the tree above:

Template 2 — iterative DFS with an explicit stack. The call stack becomes a list you manage. Anything the recursive version passed down as an argument travels with the node on the stack.

1def max_depth_iterative(root: Optional[TreeNode]) -> int:2    """Same answer, with an explicit stack of (node, depth) pairs."""3    best = 04    stack = [(root, 1)] if root else []5    while stack:6        node, depth = stack.pop()7        best = max(best, depth)8        if node.left:9            stack.append((node.left, depth + 1))10        if node.right:11            stack.append((node.right, depth + 1))12    return best

If you need preorder output from this loop, push the right child before the left one: a stack reverses what you put in, so the left child comes out first.

Template 3 — BFS, one level at a time.

1from collections import deque234def max_depth_bfs(root: Optional[TreeNode]) -> int:5    """Count levels with a queue."""6    if root is None:7        return 08    queue = deque([root])9    depth = 010    while queue:11        depth += 112        for _ in range(len(queue)):       # exactly one level per round13            node = queue.popleft()14            if node.left:15                queue.append(node.left)16            if node.right:17                queue.append(node.right)18    return depth

len(queue) is read once, when the for loop starts, so the round pops exactly the nodes of the current level even though it pushes the next level as it goes. Binary Tree Level Order Traversal is built on this line.

Complexity

Every traversal visits each node a constant number of times, so time is O(n) for n nodes.

Space is where they differ. Recursive and stack-based DFS hold one frame per level of the current path: O(h), where h is the height. That is O(log n) for a balanced tree and O(n) for a chain. BFS holds one level at a time: O(w), where w is the widest level — up to about n/2 for the bottom level of a full tree. So DFS is cheap on wide, shallow trees and BFS is cheap on narrow, deep ones.

Where it goes wrong

1. Missing null checks. node.left.val crashes with AttributeError: 'NoneType' object has no attribute 'val' on any node without a left child. Make if node is None: return ... the first line of every recursive tree function, so a child is never touched until its own call has checked it.

2. Height and depth swapped. In the tree above, node 4 has depth 2 and height 0; the root has depth 0 and height 2. If the problem is about depth, pass a counter down. If it is about height, return a value up. Mixing them compiles, runs, and is wrong.

3. Shared mutable state across branches. The classic is collecting root-to-leaf paths:

1def paths_wrong(node: Optional[TreeNode], path: list[int], out: list[list[int]]) -> None:2    if node is None:3        return4    path.append(node.val)5    if not node.left and not node.right:6        out.append(path)          # stores the same list object every time7    paths_wrong(node.left, path, out)8    paths_wrong(node.right, path, out)9    path.pop()

Every entry in out is the same list, and by the end it is empty. Store a copy — out.append(path[:]) — and always pair each append with a pop. The same bug appears throughout backtracking.

4. Recursion depth on a degenerate tree. Insert sorted values into a binary search tree and you get a chain: 10⁵ nodes, height 10⁵. Python's default recursion limit is about 1,000 frames, so the recursive version raises RecursionError. Raising the limit with sys.setrecursionlimit can crash the interpreter outright instead. The honest fix is an explicit stack or queue.

5. The wrong identity. Returning 0 for an empty subtree in a "minimum value" function makes every tree with positive values report 0. Ask: what answer makes the combine step correct when this child does not exist?