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.
Core 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. A node's fate depends only on its own value, so the order of traversal is your choice.
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: each pointer walks its own path to the root and then the other node's path, so both walk the same total (depth of p plus depth of q, plus the one step onto None). 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 is to collect p's ancestors into a set, then walk up from q until a member is found. That 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. Pass down a flag saying whether this node is currently the top of a tree:
def helper(node, is_root, to_delete, forest):
if not node: return None
deleted = node.val in to_delete
if is_root and not deleted:
forest.append(node) # survivor at the top of a tree
node.left = helper(node.left, deleted, to_delete, forest) # reassign, always
node.right = helper(node.right, deleted, to_delete, forest)
return None if deleted else node # detach from the parent
Call it as helper(root, True, set(to_delete), forest). Two details matter. A node's fate depends only on its own value, so the decision is made on the way down and only the pointer rewiring happens on the way back up. Post-order also works (record the orphaned children when a deleted node is reached), but it is not required. And the original root is a forest root only if it was not itself deleted: the is_root and not deleted test covers that case.
3. A 30-second worked example (delete and collect)
Node 5 became a root because its parent 2 was deleted. The picture traces the post-order version of the helper; the is_root version above reaches the same forest [5, 1].
4. Where you'll actually meet this
- Version control.
git merge-baseis 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). See Lowest Common Ancestor of a Binary Tree III.
Delete Nodes And Return Forest
Delete a set of values and return the roots of the remaining trees. Pass an is_root flag down, reassign children, promote orphans, and remember the original root when it survives.
Pattern: return-the-replacement recursion. Target: O(n) time, O(n) space overall (the recursion stack is O(h), the delete set and output can each reach O(n)). See Delete Nodes And Return Forest.
6. Common pitfalls
- Not reassigning the child.
helper(node.left)withoutnode.left =leaves the parent pointing at a deleted node, and most test cases will not catch it. - Losing the orphans. Whichever order you traverse, a deleted node's surviving children must be marked as roots (or appended) before the node is dropped.
- 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
- Ancestor chains are linked lists. With parent pointers, LCA is list intersection and the pointer-switch equalises path lengths.
- Return what replaces the node, and make the caller reassign. This one habit removes an entire class of tree-mutation bug.
- Order is not the point. A node's fate depends only on its own value, so decide on the way down and rewire on the way back up.
- Promote orphans when their parent is deleted, by passing the flag down to the children.
- Handle the root explicitly. It is the one node with no parent to reassign it.
- Why interviewers like it: these look easy and fail on the details. Whether you reassign, and whether you track which nodes are roots, tells them how carefully you reason about mutation.
Order: Lowest Common Ancestor of a Binary Tree III, then Delete Nodes And Return Forest.
Delete Nodes And Return Forest
Core idea: Carry one fact downward,
is_root: "is this node currently the top of a tree?" It is true at the original root and true for any node whose parent was just deleted. A node becomes a new forest root exactly when it survives and itsis_rootflag is true. To detach a deleted node, the recursion returnsNoneto the parent, which stores that result back into its child pointer.
Problem, rephrased
HR is running a layoff round on the company org chart, rooted at the CEO. You're given the root of a binary tree in which every node carries a distinct value (an employee ID) and a list to_delete of the IDs being let go. When a manager is removed, their reports are not. Each surviving child simply stops reporting to anyone, and the chart splinters into a forest of independent teams.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson