Pick two nodes in a tree and walk up from each one toward the root. The first node where the two paths meet is their lowest common ancestor. This page finds it three ways: a recursion that passes answers up the tree, a shortcut for search trees, and binary lifting, which answers many queries in a few jumps each.
Each call asks one subtree a question: did you find p, q, or both? A call returns None if it found neither, returns p or q when it lands on one, and returns itself when p and q come back from different sides. The numbers are only labels, so this works on any binary tree. Click two nodes to set p and q.
How to read this: Each circle is a node; the dashed rings mark p and q. Labels on the lines show what each child reports back to its parent: ∅ means it found nothing (or the spot is empty).
Try this: Press Step and follow the labels climbing up the lines; then click two leaves on opposite sides.
Post-order means a node decides only after both children have reported. The first node to hear back from both sides has p on one side and q on the other, so no deeper node can hold both. Above it only one side is ever non-empty, and every caller passes the answer up unchanged.
If p is an ancestor of q, the search stops at p and never looks below it. No node gets two answers, the root returns p, and p is correct because a node counts as its own ancestor. This shortcut assumes both p and q are in the tree.
A tree with n nodes has n + 1 empty child slots, so the recursion makes at most 2n + 1 calls. The stack holds one frame per level, the same way the Hanoi stack does in 005 · Recursion & fractals.
In a binary search tree everything left of a node is smaller and everything right of it is larger. That order tells you where p and q are without searching. Start at the root and walk down while both values point the same way. The first node where they disagree is the answer.
How to read this: Nodes are placed left to right by value. The dashed p and q lines mark their columns, and the gold band covers every value between them; the walk goes down until it lands inside the band.
Try this: Click two nodes far apart, then two close together, and compare how deep the walk goes.
The tree is drawn in sorted order, so each node sits in the column of its value. The gold band covers the values from p to q. While both targets lie on one side of a node, the walk stays outside the band. The first node it reaches inside the band, or on its edge, separates p from q, so it is their deepest shared ancestor.
The walk visits one node per level, so it costs O(h). On a balanced tree h is about log₂ n. Inserting values in sorted order builds a chain with h = n − 1.
When one tree gets thousands of queries, it pays to prepare. Store each node's parent and depth, and an answer takes two walks: lift the deeper node until the depths match, then lift both together until they meet. Binary lifting also stores each node's 2nd, 4th, 8th, … ancestor, so each walk becomes a few jumps. Click two nodes to set u and v.
How to read this: u and v are two pointers climbing toward the root. Each curved arrow is one jump; its label says how many levels (2³ = 2 × 2 × 2 = 8).
Try this: Toggle Parent walk and Binary lifting on the same pair and compare Loop iterations.
How to read this: Row 2ᵏ, column x holds the node you reach by climbing 2ᵏ levels up from node x. The first row is just each node's parent.
The 2k-th ancestor is the 2k−1-th ancestor of the 2k−1-th ancestor, so each row of the table is built from the row above. The root points to itself, which keeps every jump inside the tree.
Any distance d is a sum of distinct powers of two: its binary digits. Lifting u by d takes one jump per 1-bit, at most LOG jumps.
In the second loop u and v jump by 2k only when they would land on different nodes, so they always stay below the LCA. After trying every k from large to small they sit just under it, and one parent step gives the answer.
The table costs n × LOG entries, built once. A tree is a connected graph with no cycles, the kind explored in 002 · Graphs, and the parent walk is simply following edges toward the root.