Binary Trees

Recursive return contracts, traversal orders, the global-answer pattern and LCA.

Trees are the most common data structure in coding rounds after arrays and hash maps. Nearly every tree problem is solved the same way: define what a recursive call returns for a subtree, then combine the answers from the left and right children. Once you think in those terms, most tree questions become short.

The node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

The recursive mindset

For any tree problem, answer three questions before writing code:

What does solve(node) return? A height, a sum, a boolean, a pair of values?
What is the base case? Usually node is None.
How do I combine solve(node.left) and solve(node.right) with node.val?

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

Complexity is almost always O(n) time (each node visited once) and O(h) space for the recursion stack, where h is the height. That's O(log n) for a balanced tree and O(n) for a skewed one.

Two directions of information flow

Bottom-up (return values): children compute something and pass it up. Use it for height, diameter, balanced checks and subtree sums.

Top-down (parameters): the parent passes state down. Use it for path sums from the root, the maximum value seen so far, and depth.

def good_nodes(root):
    def dfs(node, max_so_far):
        if node is None:
            return 0
        good = 1 if node.val >= max_so_far else 0
        m = max(max_so_far, node.val)
        return good + dfs(node.left, m) + dfs(node.right, m)
    return dfs(root, float("-inf"))

The "global answer" pattern

Sometimes the answer at a node is not what you return to the parent. For diameter and max path sum, the best path can bend through a node, but a parent can only extend a straight path. So the function returns one thing and updates a separate best-so-far.

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)       # path bending through this node
        return 1 + max(l, r)          # straight path a parent can extend
    height(root)
    return best

[!INTERVIEW] Say the return contract out loud "My helper returns the height of the subtree; separately, I track the longest path that bends at any node." That one sentence shows the interviewer you understand the subtle part, before you write any code.

Traversal orders

from collections import deque

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):          # exactly this level's nodes
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

Iterative inorder

Interviewers sometimes ask for an iterative version, either to avoid deep recursion or just to see you manage a stack by hand.

def inorder(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                 # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

Lowest common ancestor

A classic that tests whether you can reason about return values:

def lca(node, p, q):
    if node is None or node is p or node is q:
        return node
    left, right = lca(node.left, p, q), lca(node.right, p, q)
    if left and right:
        return node             # p and q are on different sides
    return left or right

Treating a tree as a graph

When you need to move up as well as down ("all nodes at distance k", "time to infect the whole tree"), build a parent map or an adjacency list in one pass, then run BFS from the start node.

Edge cases to test

Empty tree (root is None)
A single node
A skewed tree, like a linked list. Recursion depth hits n, which overflows Python's default limit of about 1000 for large inputs.
Negative values, which matter for path sums and max path sum

[!TIP] Practice Maximum Depth · Invert Binary Tree · Diameter · Right Side View · Lowest Common Ancestor · Construct from Preorder & Inorder · All Nodes Distance K · Max Path Sum