Pocket Gems Interview Question
2. Given 2 simple nodes in a binary tree, write a method to return their youngest common ancestor (linear time). Simple node = data, left child, right child.
Interview Answer
Anonymous
Nov 10, 2013
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 }