[1] / \ [2] [3] / \ / \ [4] [5] [9] [10] / / \ [8] [6] [7]

say

n1,n2 = 8,3 => Common Ancestor =1

n1,n2 = 8,6 => Common Ancestor =2

n1,n2 = 7,6 => Common Ancestor =5

__Method 1)__

logic : when traversing from root node,

keep paths for both n1 & n2.

ex1:

p1 : 1,2,4,8

p2 : 1,3

last common value in path is LCA=1

ex2:

p1 : 1,2,4,8

p2 : 1,2,5,6

last common value in path is LCA=2

Algorithm :

FindPath ( root, vector<int> &path, int N ) { path.push_back(root->key) if(root->key = N) return 1; if ( (root->left && findPath( root->left, path, N) ) | | (root->right && findPath( root->right, path, N) ) return 1; path.pop_back(); //if path is not in this subtree return 0; } CommAncsestor( root , n1, n2 ){ vector <int> p1,p2; int i; if (!findPath(root, path1, n1) || !findPath(root, path2, n2)) return -1; for(i=0; i< path1.size() && i<path2.size(); i++){ if(path1[i] != path2[i]) break; } return path1[i-1]; }

__Method 2)__

Now think for a way where

ex:1)

when n1=8, n2=3.

while we call from root =1 , 8 will return from left subtree and 3 will return from right subtree.

so we can say CommonAncestor is 1.

ex:2) n1=8, n2= 6

for previous call, 8 and 6 will be returned from leftsubtree, while in right subtree 6 is not there , hence it will return NULL.

so if one subtree return Null, go and search in similar way as ex:1) in other subtree

so here for

for root=1, Leftsubtree=8, rightsubtree=NULL.

call leftsubtree

root = 2 its leftsubtree return 8, and rightsubtree returns 6. hence Common Ancestor is 2.

struct Node *findLCA(struct Node* root, int n1, int n2) { if (root == NULL) return NULL; if (root->key == n1 || root->key == n2) return root; Node *left_lca = findLCA(root->left, n1, n2); Node *right_lca = findLCA(root->right, n1, n2); if (left_lca && right_lca) return root; return (left_lca != NULL)? left_lca: right_lca; }

Working Code can be Found at http://ideone.com/J7gzfk

**Least Common Ancestor LCA of Binary Search Tree **

Say binary search is as given below

[7] / \ [6] [9] / / \ [5] [8] [10]

n1,n2 = 8,10 => Common Ancestor =9

n1,n2 = 8,6 => Common Ancestor =7

n1,n2 = 5,6 => Common Ancestor =6

as this tree is BST with property that leftSubTree < Parent < RightSubTree

we can use it to get CommonAncsestor.

now as we start traversing from root.

if root < n1 & root < n2 then CommonAncestor lies in Right sub tree of Root.

say in example 1) with 8,10.

if root > n1 & root > n2 then CommonAncestor lies in left sub tree of root

say in example 3) with 5,6

else root itself is CommonAncestor when root < n1 but root > n2. or root > n1 but root < n2

say in example 2) with 6,8.

struct node *CommonAncestor (struct node* root, int n1, int n2) { if (root == NULL) return NULL; if (root->data > n1 && root->data > n2) return CommonAncestor(root->left, n1, n2); else if (root->data < n1 && root->data < n2) return CommonAncestor(root->right, n1, n2); return root; }

Time complexity of above solution is O(h) where h is height of tree.

Space Complexity O(h) due to function call stack for recursive function calls.

We can avoid extra space using iterative solution.

Algorithm for iterative

struct node *CommonAncestor(struct node* root, int n1, int n2) { while (root != NULL) { if (root->data > n1 && root->data > n2) root = root->left; else if (root->data < n1 && root->data < n2) root = root->right; else break; } return root; }

Working Code :

// A recursive C program to find LCA of two nodes n1 and n2 By Gohired.in #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* left, *right; }; struct node *commonAncestor2(struct node* root, int n1, int n2) { while (root != NULL) { if (root->data > n1 && root->data > n2) root = root->left; else if (root->data < n1 && root->data < n2) root = root->right; else break; } return root; } struct node *commonAncestor(struct node* root, int n1, int n2) { if (root == NULL) return NULL; if (root->data > n1 && root->data > n2) return commonAncestor(root->left, n1, n2); else if (root->data < n1 && root->data < n2) return commonAncestor(root->right, n1, n2); return root; } struct node* newNode(int data) { struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = node->right = NULL; return(node); } int main() { struct node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int n1 = 10, n2 = 14; struct node *t; t = commonAncestor(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); n1 = 14, n2 = 8; t = commonAncestor(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); n1 = 10, n2 = 22; t = commonAncestor(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); printf("------Out put with Iterative Mehtod --------\n"); n1 = 10, n2 = 14; t = commonAncestor2(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); n1 = 14, n2 = 8; t = commonAncestor2(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); n1 = 10, n2 = 22; t = commonAncestor2(root, n1, n2); printf("LCA of %d and %d is %d \n", n1, n2, t->data); getchar(); return 0; }

Output

LCA of 10 and 14 is 12

LCA of 14 and 8 is 8

LCA of 10 and 22 is 20

——Out put with Iterative Mehtod ——–

LCA of 10 and 14 is 12

LCA of 14 and 8 is 8

LCA of 10 and 22 is 20

Working Code http://ideone.com/v1ziEj