Recursive tree patterns

Trust the recursion

A tree is made of smaller trees: every node is the root of its own subtree. So a tree question can usually be answered by asking the same question about the left subtree and the right subtree, then combining the two answers at the current node. You do not trace every call in your head. You only check three things: the base case (what does an empty tree return?), the combine step (given correct answers from both children, is my answer correct?), and that each call is on a smaller tree.

There are two directions of information. Values can flow UP (a child returns its height to its parent; this is postorder thinking) or DOWN (a parent passes the remaining target sum to its children as an argument; this is preorder thinking). Many problems need both.

Height and diameter

The height of a tree (counted in nodes here) is 1 + the larger of the two child heights, with 0 for an empty tree. The diameter is the number of EDGES on the longest path between any two nodes. That path does not have to pass through the root. At each node, the longest path that bends at this node goes down the left side and down the right side, so its length is left_height + right_height. The diameter is the largest such value over all nodes.

The trick is to compute both at once. The helper returns the height to its parent and, as a side effect, updates a best-so-far variable. That is one visit per node: O(n) time and O(h) stack space.

def diameter(root):
    best = 0

    def height(node):              # height in nodes
        nonlocal best
        if node is None:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)   # edges on the path bending here
        return 1 + max(left, right)

    height(root)
    return best

print(diameter(build([1, 2, 3, 4, 5])))   # Output: 3  (4 -> 2 -> 1 -> 3)

Is the tree balanced, in O(n)

A tree is height-balanced when, at EVERY node, the left and right heights differ by at most 1. The slow way calls a separate height() function at every node; each call walks the whole subtree again, which is O(n²) on a skewed tree. The fast way returns the height upward and uses a special value, −1, to mean "already unbalanced below". As soon as a child reports −1, pass −1 straight up.

def check(node):
    if node is None:
        return 0
    left = check(node.left)
    if left == -1:
        return -1
    right = check(node.right)
    if right == -1 or abs(left - right) > 1:
        return -1
    return 1 + max(left, right)

def is_balanced(root):
    return check(root) != -1

print(is_balanced(build([3, 9, 20, None, None, 15, 7])))        # Output: True
print(is_balanced(build([1, 2, 2, 3, 3, None, None, 4, 4])))    # Output: False

Passing values down: path sum

Path sum asks: is there a path from the root down to a LEAF whose values add up to a target? Pass the remaining amount down. At each node subtract its value; at a leaf, check whether the remaining amount equals the leaf's value. Values can be negative, so you cannot stop early just because the running total passed the target.

def has_path_sum(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:      # a leaf
        return node.val == target
    rest = target - node.val
    return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)

t = build([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1])
print(has_path_sum(t, 22), has_path_sum(t, 26), has_path_sum(t, 9))   # Output: True True False

Changing and comparing trees

Inverting (mirroring) a tree swaps the left and right child of every node. The recursive version is three lines: invert both subtrees, then swap them. Two trees are the same when both are empty, or both roots have equal values and their left subtrees are the same and their right subtrees are the same. A tree is symmetric when its left subtree is a mirror of its right subtree: compare a.left with b.right and a.right with b.left.

def invert(node):
    if node is None:
        return None
    node.left, node.right = invert(node.right), invert(node.left)
    return node

def is_mirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    return a.val == b.val and is_mirror(a.left, b.right) and is_mirror(a.right, b.left)

s = build([1, 2, 2, 3, 4, 4, 3])
print(is_mirror(s.left, s.right))   # Output: True  (this tree is symmetric)

Cost

Each of these functions visits every node at most once with O(1) work there: O(n) time. The extra space is the recursion stack, O(h): O(log n) for a balanced tree, O(n) for a skewed one. For trees deeper than about 1,000 levels Python raises RecursionError, so mention an iterative version (with a stack) in the interview.

Common mistakes

• Thinking the diameter always passes through the root. Fix: update a best value at EVERY node.
• Mixing edges and nodes in the diameter. With heights in nodes, left + right is already the number of edges.
• Checking balance only at the root. Fix: every node must satisfy the rule; the −1 signal handles this.
• Treating any node as the end of a path in path sum. The path must end at a leaf (no children). An empty tree has no path, even for target 0.
• Swapping children with two separate assignments: node.left = invert(node.right) followed by node.right = invert(node.left) uses the already changed left. Fix: swap in one tuple assignment.