Finding LCA using Recursion

Finding LCA recursively

The idea of this algorithm is to recursively traverse the left sub-tree and right sub-tree and return each node to its parent. The node that we return to the parent can either be NULL or one of the nodes whose LCA we are trying to find. If the nodes returned to the parent come from the left and the right sub-tree, the parent is the lowest common ancestor. If both come from the same sub-tree then one of the nodes is the lowest common ancestor.

LCA_Recursive

Time complexity of finding the lowest common ancestor of nodes in a binary tree : 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).


C++14 Finding the Lowest Common Ancestor(LCA) recursively

#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
Copyright (c) 2019-2020, Algotree.org.
All rights reserved.