How does finding a lowest common ancestor differ when nodes carry parent pointers versus when they do not?

## Two different worlds The lowest common ancestor of two nodes is the deepest node whose subtree contains both, with a node counted as its own ancestor. Which algorithm you reach for is decided by one structural fact: **can you move upward?** That single bit changes the complexity, the space profile and the failure modes. A useful setting: a revision store keeps a history where every revision records the single revision it was derived from, and no revision has two parents. That history is a tree. Given two revisions, you want their nearest common ancestor — the last shared state, the base you would diff both sides against. ## When nodes carry parent pointers Each node knows its parent, so each node determines a unique chain up to the root. Two chains starting from different nodes must merge somewhere (at worst at the root) and, once merged, never separate again. The answer is the merge point. The naive attempt — advance both cursors upward one step at a time and wait for them to coincide — is wrong when the depths differ: the deeper cursor is permanently behind, and the two can sail past each other without ever being equal at the same instant. The fix is to align first: 1. Compute `depth(a)` and `depth(b)` by walking each to the root: `O(h)`. 2. Lift the deeper cursor by `|depth(a) - depth(b)|` steps. 3. Advance both one step at a time; the first time they are the same node, stop. Total time `O(h)`, extra space `O(1)`. If depth is already stored on each node — natural in an append-only history, where a new revision's depth is its parent's plus one — step 1 vanishes and the setup is `O(1)`. The alternative shape trades space for simplicity: insert every ancestor of `a` into a set, then walk `b` upward and return the first node already in the set. Also `O(h)` time, but `O(h)` memory. It reads more clearly and is the version most people write under time pressure; the two-cursor walk is the one to reach for when the chain is long or memory is accounted for. ## When you can only go down With only child links from a root, every algorithm must start at the top. The standard recursion is post-order and returns a node rather than a boolean: - An empty subtree returns nothing. - A node that *is* one of the targets returns itself. - Otherwise, recurse into both children. If **both** return non-null, the two targets were found on opposite sides, so the current node is the lowest common ancestor — return it. If exactly one returns non-null, pass that result upward unchanged. If neither does, return nothing. The upward-propagated value is doing double duty: below the answer it means "a target lives here"; at and above the answer it means "the answer is here". That overloading is what makes the code short and what makes it subtle to explain. Cost: `O(n)` time — you cannot prove a subtree is target-free without visiting it, so worst case is every node, even when both targets sit near the root. Space is `O(h)` for the call stack, which is `O(log n)` on a balanced tree and `O(n)` on a degenerate chain. **Recursion depth is space**, and a candidate who calls this algorithm `O(1)` space has skipped the stack. ## The failure mode worth naming The downward recursion assumes both targets are in the tree. Give it a target that is absent and it returns the other one — a perfectly plausible-looking node that is not an ancestor of anything you asked about. Nothing in the algorithm distinguishes "found the meeting point" from "found the only target there was". If the inputs are not trusted, either verify presence with a separate traversal, or thread a found-count through the recursion and report the pair only when the count is two. The upward walk has the same class of problem in a different dress: a node from a different tree walks up to *its* root and simply never meets the other chain, so a null result must be handled rather than assumed impossible. ## Choosing If parent pointers exist, use them: `O(h)` beats `O(n)` and the constant factors are pointer hops. If they do not exist, adding a parent field is a real design change — it costs memory per node and it must be maintained on every structural mutation, which is a new invariant for every write path to honour. Judge it against how often ancestor queries actually run. Also compare against the ordered shortcut: on a search tree, key comparisons already give you an `O(h)` downward walk with no parent pointers at all, because the ordering supplies the routing information that a general binary tree lacks.