Lowest common ancestor of a Binary Search Tree
Posted by guptaradhesh on May 16, 2013
Worst case O(n)
1.
2 3
4
5
6
7
8

Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p  root == q) return root;
Node *L = LCA(root>left, p, q);
Node *R = LCA(root>right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees
}

—
reference: here
Advertisements
Leave a Reply