SeniorCodeOccasionalNot answered yet
Lowest common ancestor in a tree with parent pointers, O(1) space
Each node has parent, left, right. The tree is NOT a search tree. Return the lowest common ancestor of two given nodes using O(1) extra space.
Requirements:
- O(h) time where
his the tree height; O(1) extra space (no sets, no recursion stack).
struct Node { Node* parent; Node* left; Node* right; };
Node* lca(Node* a, Node* b) {
// your code here
}Write the implementation.
Compute each node's depth by walking up via parent to the root. Advance the deeper node upward by the depth difference so both are level, then walk both up in lockstep until the pointers meet — that node is the LCA. O(h) time, O(1) space, no extra structures.
- ✗Using a hash set of ancestors, violating the O(1) space requirement
- ✗Assuming a binary search tree and comparing values, which fails on a general tree
- ✗Forgetting to equalize depths before walking up in lockstep
- →How do you compute the depths without extra storage?
- →What is the O(d) variant using exponential upward steps?
Contents
Task
Find the LCA of two nodes in a parent-pointer tree in O(h) time and O(1) space.
Solution
struct Node { Node* parent; Node* left; Node* right; };
static int depth(Node* n) { int d = 0; for (; n; n = n->parent) ++d; return d; }
Node* lca(Node* a, Node* b) {
int da = depth(a), db = depth(b);
while (da > db) { a = a->parent; --da; } // equalize depths
while (db > da) { b = b->parent; --db; }
while (a != b) { a = a->parent; b = b->parent; }
return a; // meeting point = LCA
}Key points
- Compute depths by walking up
parent, no extra memory. - Equalize depths, then walk up in lockstep until they meet.
- O(h) time, O(1) space — distinct from the recursive and the ancestor-set approaches.
Contents
