Algotree > Algorithms > Lowest Common Ancestor (LCA) > Finding LCA in a binary tree using Recursion

Finding LCA in a binary tree using Recursion

LCA_Recursive

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.

LCA_Recursive
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

#include <iostream>
#include <stack>

using namespace std;

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

Node * GetLCA (Node * root, Node * p, Node * q) {

    if (root == nullptr || root->data == p->data || root->data == q->data)
        return root;
 
    Node * left_lca  = GetLCA (root->left,  p, q); 
    Node * right_lca = GetLCA (root->right, p, q); 

    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 node_1(1, nullptr, nullptr);
    Node node_7(7, nullptr, nullptr);
    Node node_12(12, nullptr, nullptr);
    Node node_13(13, nullptr, nullptr);
    Node node_20(20, nullptr, nullptr);
    Node node_15(15, &node_13, nullptr);
    Node node_3(3, &node_1, nullptr);
    Node node_18(18, &node_15, &node_20);
    Node node_5(5, &node_3, &node_7);
    Node node_16(16, &node_12, &node_18);
    Node root(9, &node_5, &node_16);

    cout << "LCA of (1, 13)  : " << GetLCA(&root, &node_1, &node_13)->data << endl;
    cout << "LCA of (3, 7)   : " << GetLCA(&root, &node_3, &node_7)->data << endl;
    cout << "LCA of (12, 20) : " << GetLCA(&root, &node_12, &node_20)->data << endl;
    cout << "LCA of (15, 18) : " << GetLCA(&root, &node_15, &node_18)->data << endl;

    return 0;
}

Output

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