Finding LCA in a binary tree using Recursion

Finding the Lowest Common Ancestor in a binary tree recursively

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

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


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.