LCA and Restructuring

What is this?

Two people trace their family trees back through their parents. If they walk at the same pace they will not meet, because one may be further from the common ancestor than the other. But if each, on reaching the top, switches to the other's starting point, they will have walked identical total distances — and they meet exactly at the first ancestor they share.

That is the first problem. The second is quieter and trickier: remove some nodes from a tree and hand back the pieces that survive, with no dangling references left behind.

💡 Fun fact: Lowest Common Ancestor III — the variant where nodes carry parent pointers — is the linked-list intersection problem in disguise. Each node's chain of ancestors is a linked list ending at the root, and two such chains merge at the LCA exactly as two lists merge at their intersection. The pointer-switching trick that equalises path lengths is identical, which is why solving one teaches the other for free.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line idea: when parent links exist, an ancestor query becomes a two-list intersection. When you delete nodes, a recursive call must return what should replace the node it was given, and the parent must reassign — that reassignment is what keeps the tree consistent.

---

1. Meeting in the middle

def lowest_common_ancestor(p, q):
    a, b = p, q
    while a is not b:
        a = a.parent if a else q       # exhausted → restart from the other side
        b = b.parent if b else p
    return a                            # meet at the LCA (or None if unrelated)

Why it terminates: if p is d1 steps from the LCA and q is d2, then pointer a walks d1 + (depth of q) and pointer b walks d2 + (depth of p) — and both totals are equal. They arrive together. If the two nodes are in different trees entirely, both pointers reach None simultaneously and the loop exits with None, which is the correct answer.

The alternative — collect p's ancestors into a set, then walk up from q until a member is found — is O(h) space and perfectly acceptable to offer first.

2. Return the replacement

The deletion problem is where a small habit prevents a subtle bug. A helper must return the node that should occupy this position after processing, and the caller must store it:

def helper(node, to_delete, forest):
    if not node: return None
    node.left  = helper(node.left,  to_delete, forest)     # reassign, always
    node.right = helper(node.right, to_delete, forest)
    if node.val in to_delete:
        if node.left:  forest.append(node.left)            # orphans become roots
        if node.right: forest.append(node.right)
        return None                                        # detach from the parent
    return node

Two ordering details matter. Recurse before deciding, so children are already processed and any new roots among them are recorded before the current node vanishes. And the original root is a root only if it was not itself deleted — a case worth checking explicitly rather than assuming.

---

3. A 30-second worked example (delete and collect)

Node 5 was promoted because its parent disappeared after it had been processed — which is exactly why the recursion must be post-order.

---

4. Where you'll actually meet this

• Version control. git merge-base is lowest common ancestor over the commit graph, and commits carry parent pointers, so the two-pointer variant is the natural fit.
• Org and permission hierarchies. "Who is the lowest manager over both of these people?" and "remove this department, keep its teams" are these two problems verbatim.
• Filesystem operations. Deleting a directory while preserving its contents as new top-level items is the forest problem.
• Taxonomy and category trees. Finding the nearest shared category for two products powers recommendation and breadcrumb logic.
• DOM manipulation. Removing an element while re-parenting its children requires the same "return the replacement" discipline.

---

5. Problems in this chapter

▶ Lowest Common Ancestor of a Binary Tree III

Find the LCA when nodes have parent pointers. Two pointers walking upward and switching starts, meeting after equal distance.
Pattern: two-list intersection. Target: O(h) time, O(1) space (versus the O(h)-space ancestor-set approach).

▶ Delete Nodes And Return Forest

Delete a set of values and return the roots of the remaining trees. Post-order, reassign children, promote orphans, and remember the original root when it survives.
Pattern: return-the-replacement recursion. Target: O(n) time, O(h) space.

---

6. Common pitfalls 🚫

• Not reassigning the child. helper(node.left) without node.left = leaves the parent pointing at a deleted node — and most test cases will not catch it.
• Deciding before recursing. If you delete a node before processing its children, their promotion to roots is lost.
• Forgetting the original root. If it survives, it belongs in the forest; if it is deleted, it must not be.
• Using a list for the delete set. Membership tests become O(k) each; a set makes them O(1).
• Advancing only one pointer in the LCA walk. Both must move each round or the distances never equalise.
• Assuming the two nodes are related. If they sit in different trees, both pointers must reach null together and the answer is None — the loop handles it, but only if the null-switch is written correctly.
• Comparing values instead of identity when checking whether the pointers have met — duplicates in the tree would break value comparison.

---

7. Key takeaways

1. Ancestor chains are linked lists. With parent pointers, LCA is list intersection and the pointer-switch equalises path lengths.
2. Return what replaces the node, and make the caller reassign. This one habit removes an entire class of tree-mutation bug.
3. Post-order is mandatory for deletion — children must be settled before their parent disappears.
4. Promote orphans at the moment of deletion, when both children are still reachable.
5. Handle the root explicitly. It is the one node with no parent to reassign it.
6. Why interviewers like it: these look easy and fail on the details. Whether you reassign, and whether you recurse before deciding, tells them how carefully you reason about mutation.

Order: Lowest Common Ancestor of a Binary Tree III → Delete Nodes And Return Forest.