Binary Tree

To get a tree's height: the left child tells you its height is 2, the right child says 3, and you just return 3 + 1 = 4. For tree recursion, first pin down in one sentence what each call hands back. Then keep two things apart: the value you return so the parent can keep building on it, and a final answer you can already compute at this node and simply record.

Two principles run through the whole article:

1. Trust the subproblem. Once you've written down what the function means, assume f(root.left) and f(root.right) already return the right answer, and don't follow the recursion down. It's mathematical induction: when you prove P(k+1) you use P(k), you don't re-prove it.
2. Only handle the current level, and hand the parent something it can use. What you ask your children for and what you return to your parent are the same kind of thing (your children are someone else's "current level"). If the final answer doesn't necessarily sit at the root, record it in a global at every node, and return only the part the parent can build on.

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

Brute force on trees often means "at every node, scan its whole subtree again". Checking balance, or finding the node whose left and right heights differ the most, needs the heights of both subtrees at every node; the direct way is to call a height function at each node. Computing a height costs O(subtree size), so:

Tree recursion avoids the repeat work because each subtree's answer comes back up with the return value: a child computes its own height and hands it to the parent, so the parent never recounts. Every node is visited a constant number of times, so time is O(n), and space is the depth of the call stack, which is the height O(h): O(log n) when balanced, O(n) for a chain.

Recognition Checklist

• The input is a TreeNode, and the answer can be assembled from "left subtree's answer + right subtree's answer + this node"
• The problem asks about height, balance, diameter, path sums, or whether a subtree has some property
• A node needs information from the path above it (the max so far, a valid value range)
• You need the lowest common ancestor of two nodes
• The input is a BST and you need to search, insert, delete, validate, or find the k-th smallest
• You're given preorder / inorder / postorder sequences to rebuild a tree, or need to turn a tree into a string and back

Before You Code

Before writing code, stand on any one node and answer these three questions:

1. What do I ask my children for? This is the return value of the recursive function. Write it as one sentence and don't change it halfway. Pin down the base case at the same time: what does an empty node return (0, True, None, negative infinity…)?
2. What do I do at this level? With both children's results in hand, what do I compute here, and do I update a global answer?
3. What do I hand to my parent? It must be the same kind of thing as question 1. If the final answer doesn't necessarily pass through the current node, you need a global variable, updated in question 2, and the return value carries only the part the parent can keep using.

Questions 1 and 3 are two sides of one thing: what you expect from your children is exactly what your parent expects from you.

Try it on LC 543 Diameter of Binary Tree.

Given a binary tree, return the number of edges on the longest path between any two nodes. A path can't visit a node twice, doesn't have to pass through the root, and can start and end at any nodes.

For example, root = [1, 2, 3, 4, 5] (1 has children 2 and 3; 2 has children 4 and 5) → 3: the longest path 4–2–1–3 has 4 nodes and 3 edges. We count edges, not nodes.

• Ask the children for: the number of nodes on the longest path that starts at the child and only goes down; call them l and r. An empty node returns 0.
• This level: the path through the current node, going down a bit on each side, has l nodes on the left, r on the right, plus this node: l + r + 1 nodes. A path has one fewer edge than nodes, so that's l + r edges. Use it to update a global best.
• Hand to the parent: the parent can attach to only one side, so return max(l, r) + 1 (the longer side plus this node). The longest path doesn't have to go through the root (it may sit entirely inside the left subtree), so best has to be global.

Step 4 turns this into code.

Maximum Depth of Binary Tree (LeetCode 104)

Given a binary-tree root, return the number of nodes on a root-to-deepest-leaf path; an empty tree has depth zero and a single root has depth one. The array below is level-order notation, with null/None marking absent children rather than extra nodes. Depth here is not an edge count.

Input: root = [1, 2, 3, 4] (1 has children 2 and 3; 4 is the left child of 2). Expected: 3.

The calls go down first (1 → 2 → 4 → 4's empty child) and return values come back up; the table lists the rows in the order each call returns.

1. Walk it by hand

2. Read the rule off the table

• An empty node returns 0 without calling anything.
• Every other row does the same thing: take the left answer and the right answer, keep the larger one, add 1 for this node.
• A node's row can only be filled after both of its children have returned, so the root's row comes last.

3. Turn each row into code

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

Core Templates

All six steps use the same approach: answer the three questions first, then check against the two principles — did you trust the subproblem, and is the return value something the parent can use?

Step 1: Trust the subproblem, combine the left and right answers

Problem: the maximum depth of a binary tree (LC 104).

Given the root of a binary tree, return how many nodes are on the path from the root down to the deepest leaf. An empty tree returns 0; a lone root returns 1.

For example, level order [1, 2, 3, 4] (4 is the left child of 2) → 3: the deepest path 1–2–4 has 3 nodes. Here we count nodes, unlike the diameter above, which counts edges.

The three questions:

• Ask the children for: the height of the left subtree and of the right subtree. An empty tree has height 0.
• This level: take the larger one and add this level.
• Hand to the parent: the height of the subtree rooted here, the same kind of thing as the first answer.

First the node definition, which all later code uses:

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

For writing tests, a helper that turns a LeetCode level-order list (None marks an empty slot) into a tree.

The rule: going left to right through the level-order list, each non-empty node claims the next two unclaimed slots, the first as its left child and the second as its right; empty slots claim nothing. Take [1, None, 2, 3]: 1 claims None and 2 (no left child, right child 2); the None is skipped; 2 claims 3 and "nothing left", so 3 is 2's left child.

def build(vals):
    # conditional expression A if cond else B: keep None, otherwise make a node
    nodes = [None if v is None else TreeNode(v) for v in vals]
    kids = iter(nodes[1:])          # from the 2nd slot on: children waiting to be claimed
    for node in nodes:
        if node:                    # only non-empty nodes have children
            # next(kids, None): take the next one; when exhausted, return the default None instead of raising
            node.left, node.right = next(kids, None), next(kids, None)
    return nodes[0] if nodes else None


assert build([]) is None
assert build([1, 2, 3]).right.val == 3
assert build([1, None, 2]).left is None
assert build([1, None, 2, 3]).right.left.val == 3

iter(...) turns the list into an iterator; each next call moves one slot forward and never goes back, so every slot is claimed once. nodes[1:] is a slice: a new list without the first element (the root has no parent, so nobody claims it).

Tests also need to turn a tree back into a level-order list, so write the reverse helper now. It visits level by level (BFS), writes None for an empty node without expanding its children, and finally drops trailing Nones, matching LeetCode's format:

from collections import deque


def to_list(root):
    out, q = [], deque([root])
    while q:
        node = q.popleft()          # popping a deque's left end is O(1); list.pop(0) is O(n)
        out.append(node.val if node else None)
        if node:
            q.extend([node.left, node.right])   # extend: append both children on the right at once
    while out and out[-1] is None:  # don't write trailing empty slots; out[-1] is the last element
        out.pop()
    return out


assert to_list(build([1, None, 2, 3])) == [1, None, 2, 3]
assert to_list(build([1, 2, 3, 4, 5])) == [1, 2, 3, 4, 5]
assert to_list(None) == []

A deque is a double-ended queue: adding or removing at either end is O(1). BFS always uses it.

The recursion itself is four lines:

def max_depth(root):                # returns: the height (in nodes) of the subtree rooted at root
    if root is None:                # smallest subproblem: an empty tree has height 0
        return 0
    left = max_depth(root.left)     # trust that it's right; don't follow it down
    right = max_depth(root.right)
    return max(left, right) + 1     # this level only adds 1


assert max_depth(build([])) == 0
assert max_depth(build([1])) == 1
assert max_depth(build([1, 2, 3, 4])) == 3                  # the example from the statement
assert max_depth(build([1, 2, 3, 4, 5])) == 3
assert max_depth(build([3, 9, 20, None, None, 15, 7])) == 3
assert max_depth(build([1, 2, None, 3, None, 4])) == 4      # degenerate chain

While writing it, think only about the current level: how tall is the left, how tall is the right, I'm one taller than the taller one. Here is one walk through build([1, 2, 3, 4, 5]), in the order the calls return:

The calls go all the way down to the empty nodes under the leaves, and the heights come back level by level. You only need to convince yourself of this once; after that you don't unroll recursion in your head every time.

Read the complexity off the recursion tree. Time is the sum over all nodes: one call per node, O(1) each, O(n) total. Space is the number of frames on the deepest straight-down path, which is the height O(h). Calls on the same level finish and free their space before later calls reuse it, so you don't add up every node.

Variation: invert a binary tree (LC 226)

Given the root of a binary tree, swap the left and right subtrees of every node and return the root of the inverted tree. An empty tree stays empty.

For example, [4, 2, 7, 1, 3, 6, 9] → [4, 7, 2, 9, 6, 3, 1]: the root's children 2 and 7 trade places, and the children under 2 and under 7 are swapped too. You change the structure, not sort values; the implementation below modifies the existing nodes.

Think first: Using the three questions: what do you ask the children for? Does this level swap "the children's original subtrees" or "the already-inverted subtrees"? Does it matter whether the swap is written on one line or two?

def invert(root):                   # returns: the root of this subtree after inverting it
    if root is None:
        return None
    # simultaneous assignment: the right-hand side computes both results before assigning either
    root.left, root.right = invert(root.right), invert(root.left)
    return root


assert to_list(invert(build([4, 2, 7, 1, 3, 6, 9]))) == [4, 7, 2, 9, 6, 3, 1]
assert to_list(invert(build([1, 2]))) == [1, None, 2]
assert invert(None) is None

root.left = invert(root.right)
root.right = invert(root.left)

One step further: are two trees the same (LC 100)

Given the roots a and b of two trees, decide whether they are the same: same structure, and the same value at every corresponding position. Return True / False.

For example, [1, 2] and [1, null, 2] → False: both hold 1 and 2, but 2 is a left child in one and a right child in the other. Two empty trees → True. So comparing "which values appear" isn't enough.

Think first: This time the function takes two trees at once. Which two pairs are the subproblems? How many combinations of empty nodes are there, and what should each return?

def is_same(a, b):                  # returns: are the subtrees rooted at a and b the same
    if a is None or b is None:
        return a is b               # same only if both are empty
    return a.val == b.val and is_same(a.left, b.left) and is_same(a.right, b.right)


assert is_same(build([1, 2, 3]), build([1, 2, 3]))
assert not is_same(build([1, 2]), build([1, None, 2]))
assert is_same(None, None)
assert not is_same(build([1]), None)

Further still: subtree of another tree (LC 572)

Given two non-empty trees root and sub (LeetCode calls it subRoot), decide whether root has a node whose whole subtree (that node plus all its descendants) matches sub exactly in structure and values.

For example, root = [3, 4, 5, 1, 2], sub = [4, 1, 2] → True: the subtree rooted at 4 is it. If node 2 in root also has a child 0 ([3, 4, 5, 1, 2, null, null, null, null, 0]), the subtree rooted at 4 has an extra node and doesn't count → False. You can't match just part of the nodes.

Think first: Can you reuse the is_same you just wrote? Standing on one node, in which three places could the answer be? What does it cost in the worst case?

def is_subtree(root, sub):          # returns: does root's tree contain a subtree equal to sub
    if root is None:
        return sub is None          # LeetCode guarantees sub is non-empty; this just covers the edge
    if is_same(root, sub):          # the tree rooted here is the one
        return True
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)


assert is_subtree(build([3, 4, 5, 1, 2]), build([4, 1, 2]))
assert not is_subtree(build([3, 4, 5, 1, 2, None, None, None, None, 0]), build([4, 1, 2]))
assert is_subtree(build([1]), build([1]))

Step 1 recap

• What it solves: problems whose answer is "left subtree's answer + right subtree's answer + this node": height, inversion, sameness.
• The key line: return max(left, right) + 1. Write down in one sentence what the function returns, then trust that max_depth(root.left) is already right.
• What the variations change: inversion replaces "combine" with "swap left and right, return yourself"; Same Tree has the function take two trees, left with left and right with right; Subtree calls Same Tree once at every node.
• Easiest mistake: empty-node returns and assignment order. In Same Tree, one empty and one not must return False, and a is b gets it right in one go; when inverting, splitting the swap into two assignments makes the second line read a root.left that's already been overwritten.

These problems share one thing: the line for "this level" comes after both recursive calls. Move that line to the front or the middle and you get the three traversals of Step 2.

Step 2: Where this level's work goes decides the traversal

Problem: output node values in preorder, inorder, and postorder (LC 144, 94, 145).

Given the root of a binary tree, return the list of values in the order they're visited; an empty tree returns []. The three orders differ only in where the root goes: preorder is root, left, right; inorder is left, root, right; postorder is left, right, root.

For example, [1, null, 2, 3] (1 has only a right child 2, and 2's left child is 3): preorder [1, 2, 3], inorder [1, 3, 2], postorder [3, 2, 1]. None of these is level order.

The three questions:

• Ask the children for: nothing; each child outputs its own part.
• This level: output my own value.
• Hand to the parent: nothing.

The route of the recursion is fixed: come down from the parent, walk the left subtree, come back, walk the right subtree, come back again. Every node is passed three times, and which pass the "output myself" line sits on is the traversal:

def traverse(root, order):
    out = []

    def go(node):                   # returns nothing: appends this subtree's values to out in order
        if node is None:
            return
        if order == "pre":
            out.append(node.val)    # 1st pass: just came down from the parent
        go(node.left)
        if order == "in":
            out.append(node.val)    # 2nd pass: back from the left subtree
        go(node.right)
        if order == "post":
            out.append(node.val)    # 3rd pass: back from the right subtree too

    go(root)
    return out


t = build([10, 5, 15, 2, 7, 12, 20])
assert traverse(t, "pre") == [10, 5, 2, 7, 15, 12, 20]
assert traverse(t, "in") == [2, 5, 7, 10, 12, 15, 20]
assert traverse(t, "post") == [2, 7, 5, 12, 20, 15, 10]
assert traverse(None, "in") == []
t2 = build([1, None, 2, 3])                                     # the example from the statement
assert traverse(t2, "pre") == [1, 2, 3]
assert traverse(t2, "in") == [1, 3, 2]
assert traverse(t2, "post") == [3, 2, 1]

go is defined inside traverse, so it can read the outer out and order directly. out.append(...) only adds to the same list; it never assigns a new value to the name out, so no declaration is needed. (Assigning a new value to an outer variable needs nonlocal; Step 4 covers it.)

Step 1's max_depth is postorder, because it needs both children's heights first.

Iterative inorder (LC 94)

Still LC 94: given the root of a binary tree, return its inorder values; an empty tree returns []. This time, no recursion: keep your own stack.

For example, [2, 1, 3] → [1, 2, 3]. The output is exactly the same as the recursive version; only a BST's inorder is ascending, an ordinary tree's need not be sorted.

Think first: When the recursive version walks into a left subtree, the call stack remembers "which node to come back to once the left side is done". Simulating it with your own stack, which nodes go on the stack? When do you pop a node and output it? When does the loop end?

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:             # checking only the stack exits immediately
        while cur:                  # go left, saving ancestors on the way
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()           # its left side is done; now itself
        out.append(cur.val)
        cur = cur.right             # then walk its right subtree
    return out


assert inorder_iter(build([2, 1, 3])) == [1, 2, 3]               # the example from the statement
assert inorder_iter(build([1, 2, 3, 4, 5])) == [4, 2, 5, 1, 3]
assert inorder_iter(build([1, None, 2, None, 3])) == [1, 2, 3]   # right children only
assert inorder_iter(None) == []
assert inorder_iter(t) == traverse(t, "in")                      # matches the recursive version

Variation: k-th smallest in a BST (LC 230)

Given a valid BST and an integer k, return the k-th smallest value in the tree. k counts from 1, and 1 ≤ k ≤ the number of nodes. A BST means every value in a node's left subtree is smaller than it and every value in its right subtree is larger.

For example, [3, 1, 4, null, 2], k = 1 → 1. Return the value, not the node and not an index.

Think first: What property does a BST's inorder traversal have? Do you need to finish the whole inorder walk and then pick the k-th? In the iterative inorder above, which line is the right place to count?

def kth_smallest(root, k):
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()           # the next node "output" in inorder
        k -= 1
        if k == 0:                  # the k-th node "output" is the answer
            return cur.val
        cur = cur.right


assert kth_smallest(build([3, 1, 4, None, 2]), 1) == 1          # the example from the statement
bst = build([5, 3, 6, 2, 4, None, None, 1])
assert kth_smallest(bst, 1) == 1
assert kth_smallest(bst, 3) == 3
assert kth_smallest(bst, 6) == 6
assert kth_smallest(build([1]), 1) == 1

Variation: level order (LC 102)

Given the root of a binary tree, return a list of lists: the d-th inner list holds the values of all nodes on level d, left to right. An empty tree returns [].

For example, [3, 9, 20, null, null, 15, 7] → [[3], [9, 20], [15, 7]]. Unlike the traversals above, which values share a level is part of the answer.

Think first: Recursion goes "all the way down first". What visiting order does level-by-level output need? With a queue, how do you know where this level's nodes end and the next level begins?

def level_order(root):
    res, q = [], deque([root] if root else [])  # for an empty tree the queue starts empty
    while q:
        level = []
        for _ in range(len(q)):     # range is fixed before the loop: this level's size
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res


assert level_order(build([3, 9, 20, None, None, 15, 7])) == [[3], [9, 20], [15, 7]]
assert level_order(build([1])) == [[1]]
assert level_order(None) == []

LC 199 right side view: imagine standing to the right of the tree and looking top to bottom; on each level you can only see the rightmost node. Return those values from top to bottom. An empty tree returns [].

For example, [1, 2, 3, null, 5, null, 4] → [1, 3, 4]. The right side view is not "keep following right children": in [1, 2, null, 4] the root has no right child, so on the second level you see 2, and on the third you see 4.

Think first: Which node of each level does the right side view see? Can you reuse the level_order you just wrote?

def right_side_view(root):
    # list comprehension: for each level take level[-1], its last element
    return [level[-1] for level in level_order(root)]


assert right_side_view(build([1, 2, 3, None, 5, None, 4])) == [1, 3, 4]
assert right_side_view(build([1, 2, None, 4])) == [1, 2, 4]     # left nodes show when the right is missing
assert right_side_view(None) == []

Step 2 recap

• What it solves: outputting nodes in some order: preorder, inorder, postorder, level by level.
• The key line: out.append(node.val), placed before, between, or after the two recursive calls.
• What the variations change: iterative inorder replaces the call stack with your own; k-th smallest in a BST counts to k during inorder and stops; level order switches to BFS and splits levels by len(q) at the start of each level; right side view takes the last node of each level.
• Easiest mistake: writing iterative inorder as while stack. The stack is empty at the start and empty again after popping the root, so it exits early both times; the condition must be while cur or stack.

So far information either flows up from the children or just gets output in order. Some problems need information from the ancestors, which the children can't provide: that's Step 3.

Step 3: Pass ancestor information down as a parameter

Problem : count good nodes ( LC 1448 ). Given the root of a binary tree. (Pro lesson)

One step further: validate a BST (LC 98)

Given the root of a binary tree, decide whether it's a strict BST: every value in a node's left subtree is smaller than it, all of them, and… (Pro lesson)

Step 3 recap

What it solves : the current node needs information from "the path down from the root", which the children can't give and only the ancestors… (Pro lesson)

Step 4: Return straight-down paths, settle bent paths at the turn

Paths in a tree come in two kinds: Straight down : start at a node and keep going down without turning. A parent can extend it. (Pro lesson)

One step further: maximum path sum (LC 124)

Given a non-empty binary tree whose values may be negative. A path is a sequence of adjacent nodes that never repeats a node; (Pro lesson)

Variation: the return value also carries a signal — balanced binary tree (LC 110)

Given the root of a binary tree. The tree is balanced if, at every node, the heights of the left and right subtrees differ by at most 1; (Pro lesson)

Variation: return a boolean, keep the count in a global — count univalue subtrees (LC 250)

Given the root of a binary tree. A subtree (a node plus all its descendants) is univalue if all its nodes have the same value. (Pro lesson)

Variation: return two values at once — house robber on a tree (LC 337)

Given a binary tree where each node's value is the amount in that house (non-negative). (Pro lesson)

Step 4 recap

What it solves : the answer is a path that can turn at any node, or the parent needs more than one plain number. (Pro lesson)

Step 5: Return "what I found in this subtree"

Problem : the lowest common ancestor of nodes p and q in a binary tree ( LC 236 ). (Pro lesson)

If p and q might not be in the tree

Still return the lowest common ancestor of p and q, but they are no longer guaranteed to be in the tree; (Pro lesson)

One step further: LCA in a BST (LC 235)

Still return the lowest common ancestor node of p and q, but the input is guaranteed to be a BST with distinct values, and p and q are both… (Pro lesson)

One step further: inorder successor in a BST (LC 285)

Given a BST with distinct values and a node p in it, return the node that comes right after p in inorder; (Pro lesson)

Step 5 recap

What it solves : finding the lowest common ancestor of two nodes in a tree. (Pro lesson)

Step 6: When the structure changes, return the new subtree's root

Problem : insert a value into a BST ( LC 701 ). Given the root of a BST and a value val not yet in the tree, insert val and return the root… (Pro lesson)

One step further: delete a node from a BST (LC 450)

Given a BST with distinct values and a key, delete the node whose value is key and return the root afterwards. (Pro lesson)

Variation: delete leaves with a given value (LC 1325)

Given an ordinary binary tree and target, delete every leaf whose value is target. (Pro lesson)

Variation: build a tree from preorder and inorder (LC 105)

Given the preorder traversal preorder and inorder traversal inorder of the same tree, of equal length, with distinct values, and guaranteed… (Pro lesson)

Variation: serialize and deserialize (LC 297)

Design two functions: serialize(root) turns a tree into a string, and deserialize(data) turns the string back into a tree. (Pro lesson)

Step 6 recap

What it solves : problems that change the structure: insert, delete, build. (Pro lesson)

The six steps together

Step Ask the children for This level Hand to the parent Where the answer is Step 1 The subtree's answer (height, same or not) Combine left a… (Pro lesson)

Advanced: a Trie is a 26-ary tree

This implements the three operations of LC 208 Implement Trie: insert(word) : add a lowercase word. (Pro lesson)

Variation: lookup with wildcards (LC 211)

On LeetCode this is a WordDictionary class with addWord(word) and search(pattern) . (Pro lesson)

One Problem, Many Disguises

First, the problems in the table that don't appear in the main text: LC 1650 : given two different nodes p and q from the same tree, where e… (Pro lesson)

Common Pitfalls

Using node is None to mean "reached the end of a path". For a node with one child, the empty side isn't a leaf. (Pro lesson)

Say It in the Interview

State what the recursive function returns and what an empty node returns, then how this level uses the children's results, for example: I'll… (Pro lesson)