Binary Trees & BSTs

The node itself is nothing special:

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

What is special is the shape of the definition: a binary tree is either empty, or a root whose left and right children are themselves binary trees. The structure is recursive, so the algorithms want to be recursive too. Fighting that — manually managing stacks of nodes and visited flags — is how five-line problems turn into thirty-line bug farms.

When the definition of the data is self-similar, let the shape of the code mirror the shape of the data. That single sentence is most of tree mastery.

Here's the mental shift that unlocks trees. When you write a recursive function, assume it already works on any smaller tree, and only answer: given correct answers for my children, what's the answer for me?

def max_depth(root):
    if root is None:
        return 0                      # base case: empty tree
    left = max_depth(root.left)       # trust: depth of left subtree
    right = max_depth(root.right)     # trust: depth of right subtree
    return 1 + max(left, right)       # combine: me + taller child

You did not trace how max_depth(root.left) walks twenty nodes — and you must not. Tracing the recursion in your head is like checking every brick of a load-bearing wall while standing on it. The wall holds because of induction: the function is correct on size 0 (base case), and if it's correct on smaller trees it's correct on this one (combine step). That's the whole proof, and it's also the whole design method.

In an interview, narrate it exactly that way: "Assume the recursive call gives me the right answer for each subtree; my job is the combine step." It signals you design recursion rather than guess at it.

Nearly every tree function is the same form with two blanks to fill:

def solve(root):
    if root is None:
        return ???        # blank 1: answer for the empty tree
    L = solve(root.left)
    R = solve(root.right)
    return combine(root.val, L, R)   # blank 2

Picking the empty-tree answer is where bugs hide: it must be the identity for your combine step (0 for sums and max-depth, True for "all nodes satisfy...", None for built trees). If the base case feels arbitrary, your combine step is probably wrong too.

One more habit: when a node needs to both report something upward and check something locally (balanced-tree, diameter), have the recursion return the upward value and track the global answer in an outer variable or a tuple. Don't recompute subtree facts twice — that's the difference between O(n) and O(n²).

A binary search tree adds one promise to the structure: for every node, everything in the left subtree is smaller, everything in the right subtree is larger. Not just the immediate children — the entire subtrees.

That invariant buys two superpowers:

1. Directed search. At each node, compare and discard half the world, exactly like binary search:

def find(root, x):
    while root and root.val != x:
        root = root.left if x < root.val else root.right
    return root        # O(h): height, not size

2. Sorted order for free. An in-order walk (left, node, right) of a BST visits values in ascending order. Any problem that says "k-th smallest" or "validate ordering" is whispering in-order traversal at you.

Two classic traps. First, checking only node.left.val < node.val < node.right.val does not validate a BST — a grandchild can violate the promise while every parent-child pair looks fine. You must carry the full (low, high) range down. Second, all the O(h) guarantees assume the tree is reasonably balanced; insert sorted data into a naive BST and h becomes n. Say both of these out loud and you sound like someone who has been burned — in the good way.