# Finding LCA in a binary tree using Recursion

#### Finding the Lowest Common Ancestor in a binary tree recursively

The idea to find the lowest common ancestor of node A and node B is to recursively traverse the left sub-tree and right sub-tree of root and return either node A, node B, or null to every parent node at the upper level. If the nodes returned to a parent from the recursive traversal is node A and node B, then the parent node is the lowest common ancestor.

Example: We have to find the lowest common ancestor of node 1 and node 13.

Data inside the leaf node 1 matches with the data of node 1, hence
Node 1 returns node 1 to the parent node 3.
Node 3 returns node 1 to parent node 5.
Node 5 returns node 1 to parent node 9.

Data inside the leaf node 13 matches with the data of node 13, hence
Node 13 returns node 13 to the parent node 15.
Node 15 returns node 13 to parent node 18.
Node 18 returns node 13 to parent node 16.
Node 16 returns node 13 to parent node 9.

Note: Data of leaf nodes 7, 12 and 20 doesn’t match with the data of node 1 or node 13 hence each returns Null to the parent.

As the left sub-tree and the right sub-tree of the root (9) has node 1 and node 13 respectively, root (9) has to be the lowest common ancestor of node 1 and node 13.

Algorithm: GetLCA ( Root, Node A, Node B )

If ( Root == Null or Root.Data == (Node A).Data or
Â Â Â Â Â Root.Data == (Node B).Data ) then
Â Â Â Â Â return Root

LCA_From_Left = GetLCA ( Root.Left, Node A, Node B )
LCA_From_Right = GetLCA ( Root.Right, Node A, Node B )

If (LCA_From_Left != Null and LCA_From_Right != Null ) then
Â Â Â Â Â return Root
If ( LCA_From_Left == Null )
Â Â Â Â Â return LCA_From_Right
Else
Â Â Â Â Â return LCA_From_Left

Time complexity : O ( N ), where ‘N’ is the number of nodes in the tree. As this algorithm uses tree traversal like post-order where every node is visited only once, it gives us the time complexity of O ( N ).

Program for recursively finding the Lowest Common Ancestor (LCA) in a binary tree

``````class Node :

def __init__( self, data ) :
self.left = None
self.right = None
self.data = data

def GetLCA ( root, node_a_data, node_b_data ) :

if ( root == None or root.data == node_a_data or root.data == node_b_data ) :
return root

left_lca = GetLCA ( root.left, node_a_data, node_b_data )
right_lca = GetLCA ( root.right, node_a_data, node_b_data )

if (left_lca != None and right_lca != None ) :
return root
if ( left_lca == None ) :
return right_lca
else :
return left_lca

"""
Constructed binary tree is

9
/   \
5     16
/ \    / \
3   7  12  18
/          /  \
1         15   20
/
13
"""

def main():

root = Node(9)

root.left = Node(5)
root.right = Node(16)

root.left.left = Node(3)
root.left.right = Node(7)

root.left.left.left = Node(1)

root.right.left = Node(12)
root.right.right = Node(18)

root.right.right.right = Node(20)
root.right.right.left = Node(15)

root.right.right.left.left = Node(13)

print ("LCA of (1, 13)   : " + str (GetLCA( root, 1, 13 ).data))
print ("LCA of (3, 7)    : " + str (GetLCA( root, 3, 7 ).data))
print ("LCA of (12, 20)  : " + str (GetLCA( root, 12, 20 ).data))
print ("LCA of (15, 18)  : " + str (GetLCA( root, 15, 18 ).data))

if __name__ == "__main__" :
main()
``````

Output

``````LCA of (1, 13)  : 9
LCA of (3, 7)   : 5
LCA of (12, 20) : 16
LCA of (15, 18) : 18
``````
``````#include <iostream>
#include <stack>
using namespace std;

class Node{
public:
Node(int n):data(n),left(NULL),right(NULL){
}
Node * left;
Node * right;
int data;
};

Node * GetLCA(Node * root, int node_a_data, int node_b_data){

if (root == NULL or root->data == node_a_data or root->data == node_b_data)
return root;

Node * left_lca  = GetLCA(root->left,  node_a_data, node_b_data);
Node * right_lca = GetLCA(root->right, node_a_data, node_b_data);

if (left_lca && right_lca)
return root;

if (left_lca == NULL)
return right_lca;
else
return left_lca;
}

/* Constructed binary tree is
9
/   \
5     16
/ \   /  \
3  7  12   18
/          /  \
1          15   20
/
13
*/

int main() {

Node *root = new Node(9);

root->left = new Node(5);
root->right = new Node(16);
root->left->left  = new Node(3);
root->left->left->left = new Node(1);
root->left->right = new Node(7);
root->right->left = new Node(12);
root->right->right = new Node(18);
root->right->right->right = new Node(20);
root->right->right->left = new Node(15);
root->right->right->left->left = new Node(13);

cout << "LCA of (1, 13)  : " << GetLCA(root, 1, 13)->data << endl;
cout << "LCA of (3, 7)   : " << GetLCA(root, 3, 7)->data << endl;
cout << "LCA of (12, 20) : " << GetLCA(root, 12, 20)->data << endl;
cout << "LCA of (15, 18) : " << GetLCA(root, 15, 18)->data << endl;

// Deallocate the memory block in the reverse order of allocation
delete root->right->right->left->left;
delete root->right->right->left;
delete root->right->right->right;
delete root->right->right;
delete root->right->left;
delete root->left->right;
delete root->left->left->left;
delete root->left->left;
delete root->right;
delete root->left;
delete root;

return 0;
}
``````

Output

``````LCA of (1, 13)  : 9
LCA of (3, 7)   : 5
LCA of (12, 20) : 16
LCA of (15, 18) : 18
``````
``````class Node {

int data;
Node left;
Node right;

Node (int n) {
data = n;
left = null;
right = null;
}
}

class Tree {

public static Node GetLCA (Node root, int node_a_data, int node_b_data ) {

if (root == null || root.data == node_a_data || root.data == node_b_data)
return root;

Node left_lca = GetLCA (root.left, node_a_data, node_b_data);
Node right_lca = GetLCA (root.right, node_a_data, node_b_data);

if (left_lca != null && right_lca != null)
return root;

if (left_lca == null)
return right_lca;
else
return left_lca;
}

/* Constructed binary tree is

9
/   \
5     16
/ \   /  \
3  7  12   18
/          /  \
1          15   20
/
13
*/

public static void main(String[] args) {

Node root = new Node(9);

root.left = new Node(5);
root.right = new Node(16);

root.left.left  = new Node(3);
root.left.right = new Node(7);

root.left.left.left = new Node(1);

root.right.left = new Node(12);
root.right.right = new Node(18);

root.right.right.right = new Node(20);
root.right.right.left = new Node(15);
root.right.right.left.left = new Node(13);

Tree t = new Tree();

System.out.println("LCA of (1, 13)  :  " + t.GetLCA( root, 1, 13 ).data );
System.out.println("LCA of (3, 7)   :  " + t.GetLCA( root, 3, 7 ).data );
System.out.println("LCA of (12, 20) : " + t.GetLCA( root, 12, 20 ).data );
System.out.println("LCA of (15, 18) : " + t.GetLCA( root, 15, 18 ).data );
}
}

``````

Output

``````LCA of (1, 13)  : 9
LCA of (3, 7)   : 5
LCA of (12, 20) : 16
LCA of (15, 18) : 18
``````