Find the Lowest Common Ancestor Using Parent Pointers

Problem

Nodes in a rooted forest have parent pointers but no child lists and no root pointer. Given the parent relationship and two node indices, return their lowest common ancestor. If the nodes belong to different trees, return -1.

The lowest common ancestor of a node and itself is that node.

Function Contract

Implement lowestCommonAncestorWithParents(parent, first, second), where parent[i] is the parent index of node i or -1 for a root. Return a node index.

Constraints & Assumptions

• 1 <= len(parent) <= 200,000.
• 0 <= first, second < len(parent).
• Every non-root parent index is valid.
• The input is an acyclic forest; following parent pointers always reaches -1.
• Node identity is its array index, not a stored value.

Clarifying Questions to Ask

• Is a node considered its own ancestor? Yes.
• Can the nodes be in different trees? Yes; return -1.
• Are parent pointers guaranteed acyclic? Yes.
• Is extra O(height) memory allowed? It is allowed, but an O(1)-space approach is preferred.

Hint: Equalize path lengths

Measure each node's depth to its root, advance the deeper node by the difference, then move both upward until they meet or both leave their trees.

Hint: A linked-list intersection argument also works

Treat each parent chain as a linked list. Switching each pointer to the other start after reaching -1 equalizes the total distance.

Examples

• parent = [-1, 0, 0, 1, 1, 2], first = 3, second = 4 returns 1.
• With the same forest, nodes 3 and 5 return 0.
• parent = [-1, 0, -1, 2], nodes 1 and 3 return -1.
• Asking for nodes 4 and 4 returns 4.

Evaluation Focus

• Works without child lists or a supplied root.
• Handles different depths, ancestor-descendant inputs, identical nodes, and separate trees.
• Runs in O(h1 + h2) time and O(1) auxiliary space in the preferred solution.

Extensions to Discuss

1. What changes when nodes may have multiple parents in a directed acyclic graph?
2. How would repeated LCA queries be accelerated if the forest were static?
3. How would cycle detection be added for untrusted parent pointers?