• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Common Ancestor in a Binary Tree or Binary Search Tree

October 10, 2014 by Dhaval Dave

We need to find a Least Common Ancestor of Two given nodes in Binary tree.

            [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

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Binary Search Tree, Binary Tree, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Sequence Finder Dynamic Programming

LeetCode : Word Search

Handle duplicates in Binary Search Tree

Maximum sum contiguous subarray of an Array

Diagonal Traversal of Binary Tree

LeetCode: Binary Tree Maximum Path Sum

Find min element in Sorted Rotated Array (Without Duplicates)

The Magic HackerEarth Nirvana solutions Hiring Challenge

Print Power Set of a Set

Search element in a matrix with all rows and columns in sorted order

Singly linked list

VMWare SDEII Interview

Urban Ladder Written Test.

Client Server C program

Fibonacci Hashing & Fastest Hashtable

Advanced SQL Injection

Reversal of LinkedList

Hackerearth : Counting Subarrays

Closed Parentheses checker

Minimum insertions to form a palindrome

Difference between a LinkedList and a Binary Search Tree BST

Find Pythagorean Triplets in an array in O(N)

Sort an array according to the order defined by another array

Max Sum in circularly situated Values

Find if a binary tree is height balanced ?

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Templates in C++

C++ OOPs Part1

Circular Linked List

Stickler thief

Copyright © 2025 · Genesis Framework · WordPress · Log in