1. When the tree is a BST:[LeetCode Link]
Take advantage of the order info. there are four cases need to be considered
case 1: Both nodes are to the left of the tree.
case 2: Both nodes are to the right of the tree.
case 3: One node is on the left while the other is on the right.
case 4: One of the node is the root.
The implementation in C/C++
Node *LCA(Node *root, Node *p, Node *q) {
if (!root || !p || !q) return NULL;
if (max(p->data, q->data) < root->data)
return LCA(root->left, p, q);
else if (min(p->data, q->data) > root->data)
return LCA(root->right, p, q);
else
return root;
}
2. When the tree is just a binary tree:[LeetCode Link]
i using topdown approach
start from the root node, we check whether the two node is in the left subtree, or in the right sub tree. or one in right and another in left. Naive way of doing this is using if conditional statement to iterate all possibilities. A better way of doing this is using counting. A counting function that return whether two node in the right/left, or left have one or two would serve the purpose. Based on the return value of this counting function we can do the recursion to left or right.
The implementation in C/C++:
// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
if (!root) return 0;
int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
if (root == p || root == q)
return 1 + matches;
else
return matches;
}
Node *LCA(Node *root, Node *p, Node *q) {
if (!root || !p || !q) return NULL;
if (root == p || root == q) return root;
int totalMatches = countMatchesPQ(root->left, p, q);
if (totalMatches == 1)
return root;
else if (totalMatches == 2)
return LCA(root->left, p, q);
else /* totalMatches == 0 */
return LCA(root->right, p, q);
}
This solution take the worst case of O(n^2), and average case of O(n) for balanced tree.
ii using bottom up approach
The idea is back track from the leave node, when we find one of the node, we pass it to its parent's and search the other sub tree, to check whether the other node exist. if yes, the parent is the LCA, if not, we have pass the found node back to parent of the parent or just pass NULL to parent of the parents.
The implementation in C/C++
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
}
This solution only take worst case O(n)
3. When the tree is just a binary tree and we have a parent pointer:[Leetcode link]
This problem is simpler since we can trace up to the parent using the pointer. One simple solution is to traversal the node in a bottom up fashion, we using hash function to record the node in a hash map. the LCA is the one that collision happens.
The Implementation in C/C++
Node *LCA(Node *root, Node *p, Node *q) {
hash_set<Node *> visited;
while (p || q) {
if (p) {
if (!visited.insert(p).second)
return p; // insert p failed (p exists in the table)
p = p->parent;
}
if (q) {
if (!visited.insert(q).second)
return q; // insert q failed (q exists in the table)
q = q->parent;
}
}
return NULL;
}
This takes O(h) time.
Another better way of doing this is to track up to the root from two nodes, calculate the difference, walk the deeper node dh and then walk both one at a time. When they meet at LCA.
The Implementation in C/C++
int getHeight(Node *p) {
int height = 0;
while (p) {
height++;
p = p->parent;
}
return height;
}
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// swap both nodes in case p is deeper than q.
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
// invariant: h1 <= h2.
int dh = h2 - h1;
for (int h = 0; h < dh; h++)
q = q->parent;
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return NULL; // p and q are not in the same tree
}
This code takes O(h)
