Binary Tree Patterns

Every node gets asked once

LeetCode 543: Diameter of Binary Tree asks for the longest path between any two nodes, counted in edges, in a tree of up to 10,000 nodes. The obvious plan: for every node, measure how deep its left subtree goes and how deep its right subtree goes, add the two, and keep the best sum. Measuring a depth means walking the whole subtree.

Now feed it a tree shaped like a chain: 10,000 nodes, each one the left child of the one before. The top node measures a subtree of 9,999 nodes, the next one 9,998, and so on. The depth walks alone visit 9,999 + 9,998 + … + 1 = 49,995,000 nodes.

Look at what is repeated. Every subtree's depth is measured again by every one of its ancestors. But a subtree's depth is exactly what its parent needs to compute its own depth. Let each node report its depth to its parent once, check the diameter while the reports come in, and the whole job takes 10,000 visits.

That is the lesson in one sentence: every node is asked one question, once, and the design decision is which way the answer travels. It can travel up from the children, down from the ancestors, or across a level. Six moves follow from that choice:

This lesson assumes the vocabulary from Trees & Advanced Structures (root, leaf, subtree, the BST property; height is redefined below) and the recursion habits from Advanced Recursion & Backtracking: write the base case, then trust the recursive call on the smaller tree. Move 4 carries the running summary from Foundation: Arrays & Strings down a tree. A tree is a graph with no cycles, so its DFS and BFS are the ones from Graph Traversal without the visited set.

Before any move: the node, the ruler and a test tree

LeetCode gives you a TreeNode and writes trees as level-order lists, with None (printed as null) for a missing child. The helper build turns such a list into nodes, so you can run every example in this lesson:

from collections import deque

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

def build(values):
    """Build a tree from a LeetCode-style level-order list; None = no child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

Tree A, used by the first two moves, is A = build([1, 2, 3, 4, 5, None, 6]):

        1
       / \
      2   3
     / \   \
    4   5   6

Three sizes appear in every cost claim:

• n is the number of nodes.
• h is the height counted in levels: the number of nodes on the longest root-to-leaf path. That is LeetCode's "maximum depth", and it is one more than the edge-counted height from Trees & Advanced Structures: a single node has h = 1 here (height 0 there), and the empty tree has h = 0. This lesson counts levels because the code for LeetCode 104, 110 and 543 returns that number. Tree A has h = 3.
• w is the width: the most nodes on any one level. Tree A has w = 3.

Height runs from about log₂ n for a balanced tree up to n for a chain. And watch the ruler: LeetCode 543 measures a diameter in edges, so a path through k nodes has length k − 1.

What costs what. Almost every solution here visits each node once, so it takes O(n) time whatever the shape. "Trees are O(log n)" is true only for following one root-to-leaf path in a balanced search tree; a traversal touches all n nodes. The shape matters for memory. A recursive walk keeps one call frame for every node on the current root path, so its stack uses O(h) space.

Move 1: Pick the moment you visit

Smell: the answer is "the nodes in some order", or one step needs a parent handled before its children, or after them.

Predict first: a traversal of tree A printed [4, 5, 2, 6, 3, 1]. At which moment did it record each node: before its children, between them, or after them?

One walk, three moments

A depth-first walk arrives at a node, goes down the left subtree, comes back, goes down the right subtree and comes back again. So each node offers three moments to record it:

def three_orders(root):
    pre, ino, post = [], [], []
    def walk(node):
        if node is None:
            return
        pre.append(node.val)       # arriving: before either child
        walk(node.left)
        ino.append(node.val)       # between the two subtrees
        walk(node.right)
        post.append(node.val)      # leaving: after both children
    walk(root)
    return pre, ino, post

The walk is the same; only the moment changes. Each moment has a job:

• Preorder handles a parent before any descendant. Use it when the parent has something to hand down (Move 4), or to copy or serialize a tree top-down.
• Postorder handles every descendant before the parent. Use it when the parent needs its children's results (Move 3), or to free a tree.
• Inorder visits a binary search tree in sorted order, because everything left of a node is smaller and everything right of it is larger. Move 5 and the final round use this.

The walk does a constant amount of work at each node, so every order takes O(n) time. The stack holds the current root path, which is O(h) space: 20 frames for a perfectly balanced tree of about a million nodes, and a million for a chain.

When the tree is taller than the call stack

CPython stops recursion at a limit, 1000 frames by default (sys.getrecursionlimit()). Run the walk on a chain of 1,000 nodes and it raises RecursionError: maximum recursion depth exceeded. That is Python's guard, raised before the real stack can overflow. Java throws StackOverflowError instead, and C++ usually just crashes; in both, the depth where that happens depends on the thread's stack size.

There are two fixes. sys.setrecursionlimit raises the ceiling, which is fine for moderately deep trees. An explicit stack removes the recursion: the memory is still O(h), but it lives in a list you control.

Preorder is the easy one. Pop a node, record it, and push its children right first, so that the left child is on top and comes out next:

def preorder_iterative(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:             # pushed first, popped later
            stack.append(node.right)
        if node.left:              # pushed last, popped next
            stack.append(node.left)
    return out

Inorder must delay each node until its whole left subtree is done. Walk left as far as possible, stacking every node you pass. Pop the deepest one, record it, then start again from its right child:

def inorder_iterative(root):
    out, stack = [], []
    node = root
    while node or stack:
        while node:                # walk left, remembering the way back
            stack.append(node)
            node = node.left
        node = stack.pop()         # leftmost node not yet visited
        out.append(node.val)
        node = node.right          # then its right subtree
    return out

Why it works. Invariant: the stack holds exactly the ancestors whose left subtree is still in progress, deepest on top. When a node is popped, its left subtree is finished, so it is next in inorder. Its right subtree comes before any stacked ancestor, so the walk goes there next. All stacked nodes lie on one root path, which keeps the stack at h entries or fewer.

⚠️ After the pop, node = node.right hands the right child to the inner loop, which walks down its left spine first. Pushing the right child straight onto the stack skips that spine: on [1, None, 3, 2] the result is [1, 3], where it should be [1, 2, 3].

Your turn: produce postorder with a stack, without marking nodes as visited twice. Hint: swap the two push lines in preorder_iterative and it records root, right, left. What is that list backwards?

def postorder_iterative(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)       # builds root, right, left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    out.reverse()                  # left, right, root
    return out

💡 Morris traversal walks a tree inorder with O(1) extra space. It temporarily points the right pointer of each node's inorder predecessor back at the node, climbs up along that thread, then removes it. It modifies the tree while it runs, so reach for it only when O(1) space is demanded.

Which order remembers the shape?

LeetCode 297: Serialize and Deserialize Binary Tree asks you to turn a tree into a string and back. A plain list of values is not enough. The preorder 1, 2 fits both "2 is the left child of 1" and "2 is the right child of 1". The fix is to write a marker, #, for every missing child:

def serialize(root):
    out = []
    def walk(node):
        if node is None:
            out.append("#")
            return
        out.append(str(node.val))
        walk(node.left)
        walk(node.right)
    walk(root)
    return ",".join(out)

def deserialize(data):
    tokens = iter(data.split(","))
    def read():
        token = next(tokens)
        if token == "#":
            return None
        node = TreeNode(int(token))
        node.left = read()         # the left subtree's tokens come first
        node.right = read()
        return node
    return read()

serialize(A) returns 1,2,4,#,#,5,#,#,3,#,6,#,#: 6 values and 7 markers. A tree with k nodes always has k + 1 missing children, so every encoded subtree holds exactly one more marker than values.

Why decoding is unambiguous. The first token is the root. The recursive read for the left subtree takes exactly that subtree's tokens: it stops once every node it created has had both children read. The next token starts the right subtree. The iterator remembers the position, so there is no index arithmetic. Both directions take O(n) time and O(h) stack.

Level order with markers also works; it is LeetCode's own [1,2,3,null,…] format, and build is its decoder. Inorder does not work, even with markers. Inorder with markers always alternates #, value, #, value, …, #, so the markers carry no information at all:

Same string, different trees: inorder never says which value was the root. (Without markers, preorder and inorder together do determine a tree whose values are all distinct. That is LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal.)

Predict: what does serialize return for [2, None, 1]?

Move 2: Sweep level by level

Smell: the statement talks about levels, rows, the rightmost node on each level, or the nearest leaf.

A depth-first walk dives down one branch before it touches the next, so nodes of the same depth arrive at scattered times. Breadth-first search (BFS) visits nodes in order of depth. It uses a first-in, first-out queue: take a node from the front, put its children at the back.

Predict first: on tree A the queue holds [2, 3] when level 2 begins. Process node 2: remove it and add its children. What does the queue hold now, and how would you know where level 2 ends?

The snapshot

def level_order(root):
    if root is None:
        return []
    levels, queue = [], deque([root])
    while queue:
        size = len(queue)          # the queue holds exactly one level now
        level = []
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

The result for tree A is [[1], [2, 3], [4, 5, 6]].

Why it works. Invariant: at the top of the while loop, the queue holds exactly one level, left to right. Popping size nodes removes that level. Their children were appended in the same left-to-right order, so what remains is exactly the next level, in order.

Three details decide whether it works:

• Where the count comes from. In Python, for _ in range(len(queue)): is as safe as saving size first, because range evaluates len(queue) once, when the loop starts. What breaks the grouping is a condition that is checked again on every pass: an inner while queue:, which runs on into the next level, or Java's for (int i = 0; i < q.size(); i++).
• Use collections.deque. list.pop(0) shifts every remaining element, so each pop costs time proportional to the queue's length. On a wide tree the BFS becomes O(n²).
• Guard the empty tree. Without the root is None check, deque([None]) hands None to the loop.

What BFS costs

The time is O(n). The extra space is the queue. At the top of the loop it holds one level. In the middle of a level it holds the rest of that level plus the start of the next, which is always fewer than 2w nodes. So BFS needs O(w) space where DFS needs O(h), and the tree's shape decides which is smaller:

A perfect tree's last level holds (n + 1)/2 nodes, and no binary tree has a wider level than that.

One template, many level problems

The last row is where BFS beats DFS outright. The first leaf BFS meets is a shallowest one, so it can stop there. A plain DFS for the minimum depth explores the whole tree.

Your turn: the view from the right

Stand to the right of a tree and list the values you can see, top to bottom. That is LeetCode 199. Before writing code, predict the answer for [1, 2, 3, 4]:

      1
     / \
    2   3
   /
  4

Is it the right spine, [1, 3]? Then write the function with the level-order template.

def right_side_view(root):
    if root is None:
        return []
    view, queue = [], deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:              # last node of this level
                view.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return view

def right_side_view_dfs(root):
    view = []
    def walk(node, depth):
        if node is None:
            return
        if depth == len(view):             # first node met on this level
            view.append(node.val)
        walk(node.right, depth + 1)        # right before left
        walk(node.left, depth + 1)
    walk(root, 0)
    return view

Move 3: Ask the children

Smell: the answer for a node combines the same kind of answer for its left and right subtrees: height, size, sum, "is balanced", "contains a target".

Maximum depth, LeetCode 104, is the smallest example:

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

Each line has a role. The base case answers for the empty tree. The two calls ask the children. The return combines their answers with the node itself. Trust the calls: if max_depth is right for the two smaller trees, this line makes it right for this one. Because a node can answer only after both children have, this is a postorder walk.

You will also see the empty check moved to the caller, as in if node.left: before recursing. That skips the calls on empty children, but the function then needs a separate guard for an empty root. Checking at the top, as here, keeps a single base case.

The longest path problem

Predict first: here is tree D. What is its diameter in edges, and does the longest path pass through the root?

          1
         /
        2
       / \
      3   4
     /     \
    5       6

D = build([1, 2, None, 3, 4, 5, None, None, 6])

The slow version says literally what a diameter is. Try every node as the top of the path:

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

It asks max_depth about the same subtrees again and again. The depth of node 5's subtree is measured for node 3, again for node 2 and again for node 1. On the 10,000-node chain from the introduction, those calls visit 49,995,000 nodes. On a perfectly balanced tree the repetition is milder, O(n log n), but it is still repetition.

The fast version notices that max_depth already walks every subtree in postorder. Let it keep the diameter's books while it is there:

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)   # longest path whose top is node
        return 1 + max(left, right)      # what the parent asked for
    height(root)
    return best

Trace on tree D, in the order the calls finish:

Every node is visited once: O(n) time and O(h) stack. On the 10,000-node chain from the introduction h is 10,000, so in CPython this recursion raises RecursionError at the default limit (Move 1). Raise it with sys.setrecursionlimit(20_000) or run the same postorder with an explicit stack; either way the work is still 10,000 visits.

Why one pass is enough

Every path in a tree has exactly one highest node, the one nearest the root. From there it goes down into at most two subtrees, one on each side. So the longest path whose highest node is v goes as deep as possible on both sides. A subtree of height k (counted in nodes) offers a path of k edges down from v, so that path has height(v.left) + height(v.right) edges. The helper computes exactly that at every node. Every path has some highest node, so the maximum over all nodes is the diameter. Checking n candidates covers all n(n − 1)/2 paths.

The helper returns one thing, the height, which the parent needs. It records another, the best diameter, which only the final answer needs. There are three ways to carry that side result:

• a nonlocal variable, as above;
• an instance attribute such as self.best inside LeetCode's Solution class;
• a returned pair, which the parent unpacks:

def diameter_pair(root):
    def solve(node):                     # returns (height, best diameter inside)
        if node is None:
            return 0, 0
        lh, ld = solve(node.left)
        rh, rd = solve(node.right)
        return 1 + max(lh, rh), max(ld, rd, lh + rh)
    return solve(root)[1]

All three are O(n) and equally correct. The pair version has no shared state, which makes each call easy to test on its own.

The empty side is not a leaf

The base case returns the answer for an empty tree, and that value must not distort the combine step. Choose the value the combine operation ignores:

Returning 0 for "largest value" breaks on an all-negative tree. The empty children report 0, and 0 beats every real value.

⚠️ The empty-tree value can still mislead when the question is about leaves. LeetCode 111 asks for the fewest nodes on a root-to-leaf path. Copy max_depth, swap max for min, and the tree [1, 2] gets depth 1: the missing right child reports 0, and min picks it. But a missing child is not a leaf. The only leaf is 2, at depth 2. When one child is missing, the path has to go through the other one:

def min_depth(node):
    if node is None:
        return 0
    if node.left is None:          # only one way down: take it
        return 1 + min_depth(node.right)
    if node.right is None:
        return 1 + min_depth(node.left)
    return 1 + min(min_depth(node.left), min_depth(node.right))

Your turn: balanced or not

LeetCode 110: Balanced Binary Tree: a tree is height-balanced if, at every node, the heights of the two subtrees differ by at most 1. Calling max_depth at every node recomputes heights the way diameter_slow does. Write it as one postorder pass. First predict: is [1, 2, 2, 3, 3, None, None, 4, 4] balanced? Hint: return the height, or −1 as a signal that means "unbalanced somewhere below".

def is_balanced(root):
    def height(node):                    # -1 means "not balanced below here"
        if node is None:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height(root) != -1

Boss level: the best path may bend

LeetCode 124: Binary Tree Maximum Path Sum: a path is a sequence of connected nodes, each used at most once. Return the largest sum of any path. Values can be negative, so the best path may leave out a branch that costs more than it adds.

It is the diameter again, with values in place of edge counts and one extra decision: a branch whose best sum is negative is not worth taking.

def max_path_sum(root):
    best = float("-inf")                 # not 0: every value may be negative
    def gain(node):
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)   # a branch that loses money is dropped
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)   # the path that bends here
        return node.val + max(left, right)          # a path the parent can extend
    gain(root)
    return best

Trace on [-10, 9, 20, None, None, 15, 7], in the order the calls finish:

      -10
      /  \
     9    20
         /  \
        15   7

The answer is 42 = 15 + 20 + 7, a path that bends at 20 and never touches the root. The best path through the root reaches only 34.

Two expressions, two jobs. node.val + left + right is the best path whose highest node is node, and it may use both sides. The value returned to the parent is different. The parent will extend a path upward through node, and a path that enters node from above can leave through only one child. If gain returned both sides, the parent would glue three branches together at node. On [1, 2, 3, 4, 5] that bug reports 15 = 4 + 2 + 5 + 1 + 3, which uses node 2 with three neighbours. The real answer is 11 (4 → 2 → 5, or 5 → 2 → 1 → 3).

Two more traps:

• Starting best at 0. On [-3] the answer is −3, since a path needs at least one node, but best = 0 returns 0. Start at float('-inf') or at root.val.
• Clamping the wrong thing. max(…, 0) drops a losing branch, never the node itself. The node is on every path that gain(node) describes.

Why it is correct. It is the highest-node argument from the diameter. Every path has one highest node v, and the best path with that highest node takes v plus the best non-negative downward gain on each side. gain computes exactly that at every node. O(n) time and O(h) stack.

Move 4: Tell the children

Smell: a node's answer depends on the path from the root down to it: the sum so far, the values on it, the largest value seen, the depth.

This is Foundation's running summary, carried down a tree instead of along an array. One difference matters: the walk branches. When the walk finishes a node's left subtree and turns right, the summary must be what it was at the node again. Parameters give you that for free, because each call has its own remaining. A shared list has to be undone by hand.

A path must end at a leaf

LeetCode 112: Path Sum: is there a root-to-leaf path whose values add up to target? Pass down how much is still missing.

Predict first: this version looks tidy. What does it return for the tree [1, 2] (1 at the root, 2 its left child) with target 1?

def has_path_sum_buggy(node, target):
    if node is None:
        return target == 0
    return (has_path_sum_buggy(node.left, target - node.val) or
            has_path_sum_buggy(node.right, target - node.val))

Check for a leaf explicitly:

def has_path_sum(node, target):
    if node is None:
        return False
    remaining = target - node.val
    if node.left is None and node.right is None:   # a leaf: the path ends here
        return remaining == 0
    return (has_path_sum(node.left, remaining) or
            has_path_sum(node.right, remaining))

or stops at the first True, so the right subtree is skipped once the left one succeeds. O(n) time in the worst case and O(h) stack.

Collecting paths: extend, explore, undo

LeetCode 113: Path Sum II wants every such path, as a list of values. Now the state is a list, and building a fresh list at every node costs time. So share one list: append on the way down and pop on the way back up. This is the choose, explore, unchoose rhythm from the recursion lesson.

def path_sum_all(root, target):
    paths, path = [], []
    def walk(node, remaining):
        if node is None:
            return
        path.append(node.val)                     # extend the path
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            paths.append(path[:])                 # store a copy
        walk(node.left, remaining)
        walk(node.right, remaining)
        path.pop()                                # undo before going back up
    walk(root, target)
    return paths

Tree P is build([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]), with target 22:

            5
           / \
          4   8
         /   / \
        11  13  4
       /  \    / \
      7    2  5   1

The result is [[5, 4, 11, 2], [5, 8, 4, 5]].

Why it works. Invariant: when walk(node, …) starts, path holds exactly the values from the root to node's parent. The append adds node. Each child call leaves path as it found it, by the same invariant. The final pop restores it for the caller.

Two lines carry the whole technique:

• paths.append(path[:]) stores a copy. Write paths.append(path) and every entry is the same list object, which the pops empty; tree P then returns [[], []]. A shallow copy is enough, because the elements are integers.
• path.pop() undoes the append. Forget it and nodes from finished branches stay in the list, so every later path carries leftovers from earlier branches.

Cost. The walk itself is O(n). Each stored copy costs up to h, and a tree has at most (n + 1)/2 leaves, so the total is O(n·h) in the worst case, and the output itself can be that large. The stack and path use O(h). The alternative walk(child, path + [node.val]) needs no pop, but it builds a new list of up to h values at every node: O(n·h) even when nothing matches.

Your turn: carry two numbers, not the whole path

LeetCode 1026: Maximum Difference Between Node and Ancestor: return the largest |a.val − b.val| where node a is an ancestor of node b. For [8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13] the answer is 7, from |8 − 1|.

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

What does each node need to know about the path above it? Write it in one pass.

def max_ancestor_diff(root):
    def walk(node, lo, hi):
        if node is None:
            return hi - lo                        # the path above is complete
        lo = min(lo, node.val)
        hi = max(hi, node.val)
        return max(walk(node.left, lo, hi), walk(node.right, lo, hi))
    return walk(root, root.val, root.val)

Plot twist: paths that start anywhere

LeetCode 437: Path Sum III counts paths whose values add up to target, where a path may start and end at any nodes as long as it goes downward. Values can be negative.

Starting a fresh walk from every node costs O(n·h) and repeats the same additions. Instead, spot the array problem hiding on each root path. Along the path from the root to the current node, the running sums are prefix sums. A downward path that ends at the current node has sum running(node) − running(p), where p is an ancestor or the empty start. So each node asks the question from Hash Maps & Sets (Subarray Sum Equals K): how many earlier prefix sums equal running − target?

from collections import Counter

def count_paths(root, target):
    seen = Counter({0: 1})       # prefix sums on the current root path
    def walk(node, running):
        if node is None:
            return 0
        running += node.val
        count = seen[running - target]           # paths that end at node
        seen[running] += 1
        count += walk(node.left, running) + walk(node.right, running)
        seen[running] -= 1                       # node stops being an ancestor
        return count
    return walk(root, 0)

A Counter answers 0 for a missing key without storing it. The entry {0: 1} stands for the empty prefix, so paths that start at the root are counted.

Why the undo line matters. The counter must hold the prefix sums of the current node's ancestors and nothing else. Once the walk leaves a node, that node is not an ancestor of anything visited later. Leave its entry behind and a node in another branch can "extend" a path that runs sideways through a sibling.

[5, 1, 2] with target 1 has exactly one such path: node 1 on its own. Trace (counter entries at 0 left out):

The total is 1. Without the undo line, node 2 still finds 6: 1, left behind by node 1. It counts a phantom path from 1 to 2, and the total becomes 2.

Cost. O(n) expected time, since dictionary operations are expected O(1). The stack is O(h). The counter keeps a key, possibly at count 0, for every prefix sum it has met, so it can grow to O(n).

Move 5: Every ancestor sets a limit

Smell: each node must satisfy a condition relative to all of its ancestors, not just its parent. The classic is LeetCode 98: Validate Binary Search Tree: every value in a node's left subtree must be strictly smaller than the node, and every value in its right subtree strictly larger.

Predict first: this check compares each node with its children. Does it accept tree V, and is V a binary search tree?

def looks_valid(node):                 # checks parent-child pairs only
    if node is None:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return looks_valid(node.left) and looks_valid(node.right)

      5
     / \
    4   6
       / \
      3   7

V = build([5, 4, 6, None, None, 3, 7])

A correct slow version compares each node with every value in its subtrees. Every value then gets checked again by each of its ancestors, O(n·h) work in total.

The running bounds

Instead, hand each node the range its value must fall in. The root may hold anything. Going left, the parent's value becomes the new upper bound; going right, it becomes the new lower bound:

def is_valid_bst(root):
    def check(node, low, high):        # node.val must lie strictly inside (low, high)
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return (check(node.left, low, node.val) and     # left: new upper bound
                check(node.right, node.val, high))      # right: new lower bound
    return check(root, float("-inf"), float("inf"))

Trace on V:

Why it works. Invariant: when check(node, low, high) runs, (low, high) is exactly the range that every ancestor allows at this position. Each ancestor where the path went left demands "smaller than me", and each where it went right demands "larger than me". Each step can only tighten the range, because the node that sets the new bound already passed its own check. So two numbers summarize the whole path, like the running minimum in Foundation.

Edge cases:

• Strict inequalities. LeetCode 98 treats duplicates as invalid, so [2, 2, 2] is not a BST. If a variant allows duplicates on one side, loosen only that side's comparison.
• Extreme values. Values range from −2³¹ to 2³¹ − 1. Python compares an int with float('inf') exactly, so these sentinels are safe. In Java, starting from Integer.MIN_VALUE and Integer.MAX_VALUE rejects a tree that contains those values; use null or long bounds there.
• Early exit. and stops at the first subtree that fails.

O(n) time and O(h) stack.

Your turn: the inorder check

Use the other description of a BST: a binary tree is a BST (with distinct values) exactly when its inorder walk is strictly increasing. Adapt inorder_iterative from Move 1 so it stops at the first value that is not larger than the one before it. Test it on V, on [2, 2, 2] and on [2, 1, 3].

def is_valid_bst_inorder(root):
    stack, node, prev = [], root, None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev:
            return False                   # not strictly increasing
        prev = node.val
        node = node.right
    return True

Move 6: Where two paths meet

The lowest common ancestor (LCA) of nodes p and q is the deepest node that has both p and q as descendants, where a node counts as a descendant of itself. So if q lies below p, the LCA is p.

Smell: two nodes, and a question about what connects them: their common ancestor, the distance between them, the path from one to the other.

In a BST: walk down until they split

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree. Tree B is build([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]):

          6
        /   \
       2     8
      / \   / \
     0   4 7   9
        / \
       3   5

Predict first: what is the LCA of 3 and 5? Of 2 and 4? Of 2 and 8?

def lca_bst(root, p, q):
    low, high = min(p.val, q.val), max(p.val, q.val)
    node = root
    while node:
        if high < node.val:        # both targets are smaller: go left
            node = node.left
        elif low > node.val:       # both are larger: go right
            node = node.right
        else:                      # low <= node.val <= high: the paths split here
            return node
    return None

For 3 and 5: at 6 both are smaller, so go left; at 2 both are larger, so go right; at 4, 3 ≤ 4 ≤ 5, so the answer is 4.

Why it works. While both values are smaller than the node, both targets lie in its left subtree, so their lowest common ancestor lies there too. The right side works the same way. The first node whose value lies between them (inclusive) either is one of them or has them on different sides, and in both cases no deeper node holds both. O(h) time and O(1) extra space: one walk down, no recursion.

In any binary tree: report what you found

Without the ordering, a value can't tell you which way to go. So ask the children. This is LeetCode 236: Lowest Common Ancestor of a Binary Tree:

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:             # one target on each side
        return root
    return left or right           # pass up whatever was found, or None

A call returns None when its subtree holds neither target. Otherwise it returns the node the parent should keep: the LCA, if both targets are inside, or the one target that is.

Tree L is build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]):

          3
        /   \
       5     1
      / \   / \
     6   2 0   8
        / \
       7   4

Trace for p = 6, q = 4, in the order the calls finish:

For p = 5 and q = 4, the call on node 5 returns 5 at once, without looking below it. That is right: 4 is below 5, so 5 is the LCA. Had 4 been elsewhere, some higher node would have received 5 from one side and 4 from the other.

Two traps:

• Compare nodes with is, not by value. root.val == p.val is safe only when values are unique. LeetCode 236 promises that; many variants don't, and then two different nodes can hold the same value.
• The early return assumes both targets exist. If q is not in the tree, lca still returns p. LeetCode 1644: Lowest Common Ancestor of a Binary Tree II wants None in that case. Don't stop early at a target; count how many targets you actually meet, and trust the answer only if the count is 2.

O(n) time and O(h) stack.

Your turn: parent pointers, no root

LeetCode 1650: Lowest Common Ancestor of a Binary Tree III: every node has a parent field, and you are given only p and q. Find their LCA with O(1) extra space. Hint: two nodes at the same depth reach their LCA after the same number of steps up.

def lca_parent(p, q):
    def depth(node):
        d = 0
        while node:
            d += 1
            node = node.parent
        return d
    dp, dq = depth(p), depth(q)
    while dp > dq:                 # lift the deeper node first
        p, dp = p.parent, dp - 1
    while dq > dp:
        q, dq = q.parent, dq - 1
    while p is not q:              # then climb in lockstep
        p, q = p.parent, q.parent
    return p

💡 A parent map turns a tree into a graph. When a problem needs to move upward from an arbitrary node (all nodes at distance k from a target, how long a fire takes to spread from one node), record every node's parent in one traversal. Each node now has up to three neighbours, and BFS from Graph Traversal walks outward in every direction. It needs a visited set again, because you can now walk back the way you came. For two nodes, distance(p, q) = depth(p) + depth(q) − 2 × depth(LCA).

Final round: no label on the problem

Real problems don't say which move they want. For each one, decide which way the information flows, what a call receives or returns, and what the empty tree returns. Then peek.

Challenge 1: good nodes

LeetCode 1448: Count Good Nodes in Binary Tree: a node is good if no node on the path from the root to it has a larger value. Count the good nodes. [3, 1, 4, 3, None, 1, 5] has 4.

       3
      / \
     1   4
    /   / \
   3   1   5

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

Challenge 2: the kth smallest

LeetCode 230: Kth Smallest Element in a BST: return the kth smallest value, counting from 1. Collecting every value and sorting costs O(n log n) time and O(n) space. Do better, and stop as soon as you know the answer.

def kth_smallest(root, k):
    stack, node = [], root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Challenge 3: the robber moves into a tree

LeetCode 337: House Robber III: the houses form a binary tree, and robbing two directly linked houses sets off the alarm. Return the most money you can take. [3, 2, 3, None, 3, None, 1] gives 7 (3 + 3 + 1).

       3
      / \
     2   3
      \   \
       3   1

def rob(root):
    def solve(node):               # (best if node is robbed, best if it is not)
        if node is None:
            return 0, 0
        l_rob, l_skip = solve(node.left)
        r_rob, r_skip = solve(node.right)
        take = node.val + l_skip + r_skip
        skip = max(l_rob, l_skip) + max(r_rob, r_skip)
        return take, skip
    return max(solve(root))

Challenge 4: mirror image

LeetCode 226: Invert Binary Tree: swap the left and right child of every node. Which visiting orders work? Someone writes it inorder-style: invert the left subtree, swap, invert the right subtree. What goes wrong on [4, 2, 7, 1, 3, 6, 9]?

def invert(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left   # preorder: swap, then recurse
    invert(node.left)
    invert(node.right)
    return node

Test the shapes, not just the example

A slow version that follows the definition is a free test oracle. Compare it with the fast one on many small random trees:

import random

def random_tree(n):
    if n == 0:
        return None
    nodes = [TreeNode(random.randint(-5, 5)) for _ in range(n)]
    for i in range(1, n):
        while True:                          # hang node i on a free child slot
            parent = random.choice(nodes[:i])
            side = random.choice(("left", "right"))
            if getattr(parent, side) is None:
                setattr(parent, side, nodes[i])
                break
    return nodes[0]

def check(trials=500, max_n=12):
    for _ in range(trials):
        root = random_tree(random.randint(0, max_n))
        assert diameter(root) == diameter_slow(root) == diameter_pair(root)
    print("all matched")

Success means check() prints all matched. Random trees rarely produce the shapes that break tree code, so add them on purpose:

• the empty tree and a single node;
• a chain leaning left and a chain leaning right, where every node is missing a child and the recursion runs deep;
• a perfect tree, where the levels are widest;
• all values equal, which exposes comparisons by value instead of by identity;
• all values negative, which exposes sentinels such as 0 or best = 0.

Cheat sheet: smell → move

Before moving on, pick one problem from this lesson and explain it aloud from a blank editor: which way the information flows, what each call receives and what it returns, what the empty tree returns and why that value is neutral, why no path or node can be missed (the highest-node argument, or the invariant), and what the stack or queue costs on a chain and on a perfect tree. If you can do that, new tree problems become a question of choosing the direction.

Next: Heaps & Priority Queues for a tree stored in an array that always serves the smallest item first, Graph Traversal for DFS and BFS once cycles appear, and Dynamic Programming Mastery for the method behind House Robber III.