sundeepblue
2/5/2014 - 8:48 PM

## LCA, lca, lowest common ancester of a binary tree

LCA, lca, lowest common ancester of a binary tree

``````// ====================================
// LCA of a nornal Binary Tree, no parent pointers
// solution 1. But easy to TIMEOUT!
bool contain(TreeNode *root, TreeNode *p) {
if(!root) return false;
if(root == p) return true;
return contain(root->left, p) || contain(root->right, p);
}

TreeNode* LCA(TreeNode *root, TreeNode *p, TreeNode *q) {
if(!root) return NULL;
if(contain(root->left, p) && contain(root->left, q))
return LCA(root->left, p, q);
if(contain(root->right, p) && contain(root->right, q))
return LCA(root->right, p, q);
return root;
}

// ====================================
// solution 2, recursive, time O(n)
TreeNode* LCA2(TreeNode *root, Node *p, Node *q) {
if(!root) return NULL;
if(root == p || root == q) return root;
TreeNode *L = LCA2(root->left, p, q);
TreeNode *R = LCA2(root->right, p, q);
if(L&&R) return root;
if(L && !R) return L;
if(!L && R) return R;
return NULL;
}

// ====================================
// LCA of a nornal Binary Tree, has parent pointer,
// solution 1: calculate each depth, then walk up. O(1) space, O(max(height(p), height(q))) time.
struct TreeNode {
int val;
TreeNode *left, *right, *parent;
};

TreeNode* LCA(TreeNode *root, TreeNode *p, TreeNode *q) {
int depth1 = 0, depth2 = 0;
TreeNode *pp = p, *qq = q;
while(pp) {
pp = pp->parent;
++depth1;
}
while(qq) {
qq = qq->parent;
++depth2;
}
TreeNode *u = depth1 > depth2 ? p : q;
TreeNode *v = depth1 > depth2 ? q : p;
int diff = abs(depth1 - depth2);
while(diff--) t = t->parent;
while(u != v) {
u = u->parent;
v = v->parent;
}
return u;
}

// ====================================
// LCA of a nornal Binary Tree, has parent pointer,
// solution 2: use hash table. O(max(dp-dl, dq-dl)) space, O(max(dp-dl, dq-dl)) time.
// time is better than the above solution 1. trade space for time.
TreeNode* LCA(TreeNode *root, TreeNode *p, TreeNode *q) {
unordered_set<TreeNode*> hash;
...
}

// ====================================
// LCA of a Binary Search Tree (BST), no parent pointers
TreeNode* LCA3(TreeNode *root, TreeNode *p, TreeNode *q) {
if(!root) return NULL;
if(!p) return q;
if(!q) return p;
int vp = p->val, vq = q->val, vr = root->val;
if(vr < vp && vr < vq)
return LCA3(root->right, p, q);
if(vr > vp && vr > vq)
return LCA3(root->left, p, q);
return root;
}

``````