Trees cheat sheet

How trees are written on these pages

Every tree page uses one small dataclass: a value and two optional children. Test cases write a tree as a list in level order, where the children of position i sit at 2i + 1 and 2i + 2 and None marks a missing node. A helper turns that list into Nodes before the solution runs.

How deep is the deepest branch?

The depth of a tree is one more than the deeper of its two subtrees; an empty tree has depth 0. That recursion visits each node once: O(n) time, and O(h) stack for a tree of height h.

def depth(root: Node | None) -> int:
    if not root:
        return 0  # an empty branch adds nothing
    return 1 + max(depth(root.left), depth(root.right))

Is this a valid binary search tree?

Pass an allowed range down the tree. The root may be anything; a left child must be below its parent and above the parent's own lower limit, and the right side mirrors that. Any node outside its range fails. O(n) time, O(h) stack.

def is_search_tree(root: Node | None) -> bool:
    def ok(node: Node | None, low: float, high: float) -> bool:
        if node is None:
            return True
        if not low < node.val < high:
            return False
        return (ok(node.left, low, node.val)
                and ok(node.right, node.val, high))
    return ok(root, float("-inf"), float("inf"))

List a tree's values row by row

Breadth-first search with a queue. At the start of each round the queue holds exactly one row; take that many nodes, record their values and queue their children. Each node is queued and removed once: O(n) time, O(w) extra space for the widest row w.

from collections import deque


def rows(root: Node | None) -> list[list[int]]:
    out: list[list[int]] = []
    queue = deque([root] if root else [])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.val)
            queue.extend(c for c in (node.left, node.right) if c)
        out.append(row)
    return out

Are two trees identical?

Recurse on both trees together: two empty trees match, one empty and one not do not, otherwise the roots must hold equal values and both pairs of children must match. O(n) time for the smaller tree, O(h) stack.

def identical(a: Node | None, b: Node | None) -> bool:
    if a is None or b is None:
        return a is b
    return (a.val == b.val and identical(a.left, b.left)
            and identical(a.right, b.right))

Does a tree mirror itself?

A tree mirrors itself if its left and right subtrees are mirrors of each other. Two subtrees are mirrors when their roots match, the outer pair (left.left, right.right) are mirrors and the inner pair (left.right, right.left) are mirrors. O(n) time, O(h) stack.

def mirrors_itself(root: Node | None) -> bool:
    def pair(a: Node | None, b: Node | None) -> bool:
        if a is None or b is None:
            return a is b
        return (a.val == b.val and pair(a.left, b.right)
                and pair(a.right, b.left))
    return root is None or pair(root.left, root.right)

Swap every node's left and right children

Visit every node once and swap its children; the order of visits does not matter as long as each node is swapped exactly once. Recursively: swap, then recurse into both children. O(n) time, O(h) stack.

def swap_sides(root: Node | None) -> Node | None:
    if root is not None:
        root.left, root.right = root.right, root.left
        swap_sides(root.left)
        swap_sides(root.right)
    return root

Longest path between any two nodes

For each node, the longest path that bends at that node is height(left) + height(right) in edges. Compute heights bottom-up and keep the best bend seen in an outer variable. One post-order walk: O(n) time, O(h) stack.

def longest_path(root: Node | None) -> int:
    best = 0

    def height(node: Node | None) -> int:
        nonlocal best
        if node is None:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    height(root)
    return best

Is every node's left and right height within one?

Compute heights bottom-up and fail fast: return the height when a subtree is fine, or a sentinel (-1) as soon as any node is out of balance. One post-order pass, O(n) time, O(h) stack.

def within_one(root: Node | None) -> bool:
    def height(sub: Node | None) -> int:
        if sub is None:
            return 0
        left = height(sub.left)
        right = height(sub.right)
        if left < 0 or right < 0 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height(root) >= 0

What you see from the right of a tree

Walk the tree row by row with a queue and record the last value in each row. Or run a DFS that visits right children first and records the first node seen at each new depth. Both are O(n) time; the DFS uses O(h) stack.

def right_view(root: Node | None) -> list[int]:
    seen: list[int] = []

    def walk(node: Node | None, depth: int) -> None:
        if node is None:
            return
        if depth == len(seen):
            seen.append(node.val)
        walk(node.right, depth + 1)
        walk(node.left, depth + 1)
    walk(root, 0)
    return seen

The k-th smallest value in a search tree

An in-order walk of a search tree visits values in increasing order. Walk in order with an explicit stack and stop at the k-th value. O(h + k) time and O(h) space, which is much less than sorting all n values when k is small.

def kth_smallest(root: Node | None, k: int) -> int:
    stack: list[Node] = []
    node, seen = root, 0
    while True:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        seen += 1
        if seen == k:
            return node.val
        node = node.right

Closest shared ancestor in a search tree

Start at the root. If both values are smaller, the answer is in the left subtree; if both are larger, it is in the right. Otherwise the values split here (or one equals this node), so this node is the answer. O(h) time (O(log n) when balanced, O(n) for a chain), O(1) space with a loop.

def shared_ancestor(root: Node | None, a: int, b: int) -> int:
    node = root
    while node is not None:
        if a < node.val and b < node.val:
            node = node.left
        elif a > node.val and b > node.val:
            node = node.right
        else:
            return node.val
    raise ValueError("values not in the tree")

Does a root-to-leaf route add up to a target?

Subtract each node's value from the target on the way down. At a leaf, the route works if what is left is zero. Return True as soon as any branch succeeds. O(n) time, O(h) stack.

def route_hits(root: Node | None, target: int) -> bool:
    if root is None:
        return False
    left = target - root.val
    if not (root.left or root.right):
        return left == 0  # a leaf: the route ends here
    return route_hits(root.left, left) or route_hits(root.right, left)

Pre-order, in-order, post-order and level order

Pre-order visits a node before its children (copying or serialising a tree). In-order visits left, node, right (sorted output from a search tree). Post-order visits children first (sizes, heights, deleting a tree). Level order visits row by row with a queue (shortest depth, row questions). All are O(n).

Why search trees need to stay balanced

Search, insert and delete in a search tree cost O(h), the height. A balanced tree has h about log₂ n, so the operations are O(log n). Insert sorted keys into a plain search tree and it degenerates into a chain with h = n, so every operation becomes O(n). Self-balancing trees (AVL, red-black) rotate nodes to keep h = O(log n).

Recursion depth and when to walk a tree iteratively

Recursion uses one stack frame per level, so its depth equals the tree's height. On balanced trees that is about log₂ n, tiny even for millions of nodes. On a chain-shaped tree it is n, and CPython stops at about 1000 frames by default. Use an explicit stack (DFS) or queue (BFS) when the height can be large.