Find The Lowest Common Ancestor (LCA) Of Two Nodes In A Binary Tree

Given a binary tree and two nodes, x and y, find the lowest common ancestor (LCA) of x and y in it. The solution should return null if either x or y is not the actual node in the tree.

The lowest common ancestor (LCA) of two nodes x and y in a binary tree is the lowest (i.e., deepest) node that has both x and y as descendants, where each node can be a descendant of itself (so if x is reachable from w, w is the LCA). In other words, the LCA of x and y is the shared ancestor of x and y that is located farthest from the root.

For example, consider the following binary tree. Let x = 6 and y = 7. The common ancestors of nodes x and y are 1 and 3. Out of nodes 1 and 3, the LCA is 3 as it is farthest from the root.

Practice this problem

A simple solution would be to store the path from root to x and the path from the root to y in two auxiliary arrays. Then traverse both arrays simultaneously till the values in the arrays match. The last matched value will be the LCA. If the end of one array is reached, then the last seen value is LCA. The time complexity of this solution is O(n), where n is the total number of nodes in the binary tree. But the auxiliary space used by it is O(n) required for storing two arrays.

We can recursively find the lowest common ancestor of nodes x and y present in the binary tree. The trick is to find the node in a binary tree with one key present in its left subtree and the other key present in the right subtree. If any such node is present in the tree, then it is LCA; if y lies in the subtree rooted at node x, then x is the LCA; otherwise, if x lies in the subtree rooted at node y, then y is the LCA.

The algorithm can be implemented as follows in C++, Java, and Python:

C++

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118

#include <iostream>usingnamespacestd; // Data structure to store a binary tree nodestructNode{intdata;Node*left,*right; Node(intdata){this->data=data;this->left=this->right=nullptr;}}; // Function to check if a given node is present in a binary tree or notboolisNodePresent(Node*root,Node*node){// base caseif(root==nullptr){returnfalse;} // if the node is found, return trueif(root==node){returntrue;} // return true if a given node is found in the left or right subtreereturnisNodePresent(root->left,node)||isNodePresent(root->right,node);} // Function to find the lowest common ancestor of given nodes `x` and `y`, where// both `x` and `y` are present in a binary tree.// The function returns true if `x` or `y` is found in a subtree rooted at the root.// `lca` —> stores `LCA(x, y)`, and it is passed by reference to the functionboolfindLCA(Node*root,Node*&lca,Node*x,Node*y){// base case 1: return false if the tree is emptyif(root==nullptr){returnfalse;} // base case 2: return true if either `x` or `y` is foundif(root==x||root==y){// set lca to the current nodelca=root;returntrue;} // recursively check if `x` or `y` exists in the left subtreeboolleft=findLCA(root->left,lca,x,y); // recursively check if `x` or `y` exists in the right subtreeboolright=findLCA(root->right,lca,x,y); // if `x` is found in one subtree and `y` is found in the other subtree,// update lca to the current nodeif(left&&right){lca=root;} // return true if `x` or `y` is found in either left or right subtreereturnleft||right;} // Function to find the lowest common ancestor of nodes `x` and `y`voidfindLCA(Node*root,Node*x,Node*y){// `lca` stores the lowest common ancestorNode*lca=nullptr; // call LCA procedure only if both `x` and `y` are present in the treeif(isNodePresent(root,y)&&isNodePresent(root,x)){findLCA(root,lca,x,y);} // if LCA exists, print itif(lca!=nullptr){cout<<"LCA is "<<lca->data<<endl;}else{cout<<"LCA does not exist\n";}} intmain(){/* Construct the following tree 1 / \ / \ 2 3 \ / \ 4 5 6 / \ 7 8 */ Node*root=newNode(1);root->left=newNode(2);root->right=newNode(3);root->left->right=newNode(4);root->right->left=newNode(5);root->right->right=newNode(6);root->right->left->left=newNode(7);root->right->left->right=newNode(8); findLCA(root,root->right->left->left,root->right->right);findLCA(root,root->right->left->left,newNode(10));findLCA(root,root->right->left->left,root->right->left->left);findLCA(root,root->right->left->left,root->right->left);findLCA(root,root->left,root->right->left); return0;}

Download  Run Code

Java

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130

// A class to store a binary tree nodeclassNode{intdata;Node left=null,right=null; Node(intdata){this.data=data;}} classMain{// Wrapper over `Node` classstaticclassNodeWrapper{publicNode node; NodeWrapper(Node node){this.node=node;}} // Function to check if a given node is present in a binary tree or notpublicstaticbooleanisNodePresent(Node root,Node node){// base caseif(root==null){returnfalse;} // if the node is found, return trueif(root==node){returntrue;} // return true if a given node is found in the left or right subtreereturnisNodePresent(root.left,node)||isNodePresent(root.right,node);} // Function to find the lowest common ancestor of given nodes `x` and `y`, where// both `x` and `y` are present in the binary tree.// The function returns true if `x` or `y` is found in a subtree rooted at the root// `lca` —> stores `LCA(x, y)`publicstaticbooleanfindLCA(Node root,NodeWrapper lca,Nodex,Nodey){// base case 1: return false if the tree is emptyif(root==null){returnfalse;} // base case 2: return true if either `x` or `y` is foundif(root==x||root==y){// set lca to the current nodelca.node=root;returntrue;} // recursively check if `x` or `y` exists in the left subtreebooleanleft=findLCA(root.left,lca,x,y); // recursively check if `x` or `y` exists in the right subtreebooleanright=findLCA(root.right,lca,x,y); // if `x` is found in one subtree and `y` is found in the other subtree,// update lca to the current nodeif(left&&right){lca.node=root;} // return true if `x` or `y` is found in either left or right subtreereturnleft||right;} // Function to find the lowest common ancestor of nodes `x` and `y`publicstaticvoidfindLCA(Node root,Nodex,Nodey){// `lca` stores the lowest common ancestorNode lca=null; // Wrap the `lca` node, so its reference can be changed inside the// `findLCA()` methodNodeWrapper LCA=newNodeWrapper(lca); // call LCA procedure only if both `x` and `y` are present in the treeif(isNodePresent(root,y)&&isNodePresent(root,x)){findLCA(root,LCA,x,y);lca=LCA.node;} // if LCA exists, print itif(lca!=null){System.out.println("LCA is "+lca.data);}else{System.out.println("LCA does not exist");}} publicstaticvoidmain(String[]args){/* Construct the following tree 1 / \ / \ 2 3 \ / \ 4 5 6 / \ 7 8 */ Node root=newNode(1);root.left=newNode(2);root.right=newNode(3);root.left.right=newNode(4);root.right.left=newNode(5);root.right.right=newNode(6);root.right.left.left=newNode(7);root.right.left.right=newNode(8); findLCA(root,root.right.left.left,root.right.right);findLCA(root,root.right.left.left,newNode(10));findLCA(root,root.right.left.left,root.right.left.left);findLCA(root,root.right.left.left,root.right.left);findLCA(root,root.left,root.right.left);}}

Download  Run Code

Python

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798

# A class to store a binary tree nodeclassNode:def__init__(self,data,left=None,right=None):self.data=dataself.left=leftself.right=right # Function to check if a given node is present in a binary tree or notdefisNodePresent(root,node): # base caseifroot isNone:returnFalse # if the node is found, return trueifroot==node:returnTrue # return true if a given node is found in the left or right subtreereturnisNodePresent(root.left,node)orisNodePresent(root.right,node) # Function to find the lowest common ancestor of given nodes `x` and `y`, where# both `x` and `y` are present in a binary tree.# The function returns true if `x` or `y` is found in a subtree rooted at the root.# `lca` —> stores `LCA(x, y)`deffindlca(root,lca,x,y): # base case 1: return false if the tree is emptyifroot isNone:returnFalse,lca # base case 2: return true if either `x` or `y` is found# with lca set to the current nodeifroot==xorroot==y:returnTrue,root # recursively check if `x` or `y` exists in the left subtreeleft,lca=findlca(root.left,lca,x,y) # recursively check if `x` or `y` exists in the right subtreeright,lca=findlca(root.right,lca,x,y) # if `x` is found in one subtree and `y` is found in the other subtree,# update lca to the current nodeifleft andright:lca=root # return true if `x` or `y` is found in either left or right subtreereturn(left orright),lca # Function to find the lowest common ancestor of nodes `x` and `y`deffindLCA(root,x,y): # `lca` stores the lowest common ancestorlca=None # call LCA procedure only if both `x` and `y` are present in the treeifisNodePresent(root,y)andisNodePresent(root,x):lca=findlca(root,lca,x,y)[1] # if LCA exists, print itiflca:print('LCA is',lca.data)else:print('LCA does not exist') if__name__=='__main__': ''' Construct the following tree 1 / \ / \ 2 3 \ / \ 4 5 6 / \ 7 8 ''' root=Node(1)root.left=Node(2)root.right=Node(3)root.left.right=Node(4)root.right.left=Node(5)root.right.right=Node(6)root.right.left.left=Node(7)root.right.left.right=Node(8) findLCA(root,root.right.left.left,root.right.right)findLCA(root,root.right.left.left,Node(10))findLCA(root,root.right.left.left,root.right.left.left)findLCA(root,root.right.left.left,root.right.left)findLCA(root,root.left,root.right.left)

Download  Run Code

Output: LCA is 3 LCA does not exist LCA is 7 LCA is 5 LCA is 1

The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.

References: https://en.wikipedia.org/wiki/Lowest_common_ancestor