Lowest Common Ancestor in a Binary Tree in C++

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Definition of LCA (according to Wikipedia) The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants.

binary tree
Binary Tree
For the given Binary tree, if info[key1] = 15 and info[key2] = 31, it should print:
21

Pseudocode

1. Traverse the given binary tree in an preorder fashion.
2. Do if info[root] == key1 or info[root] == key2, return root
3. Traverse root->left and root->right for key1 and key2
4. if key1 and key2, both are found
5.   return (root). Since it is common to the path of both the keys key1 and key2;
6. end

Code Implementation

Let the given tree be:

Binary Tree
//
//  main.cpp
//  Lowest Common Ancestor (LCA)
//
//  Created by Himanshu on 31/10/21.
//

#include <iostream>
#include <queue>
using namespace std;

struct node {
    int info = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->info = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}


Node* lca (Node *root, int n1, int n2) {
    if (root == NULL) {
        return NULL;
    }
    
    if (root->info == n1 || root->info == n2) {
        return root;
    }
    
    Node *leftLCA  = lca(root->left, n1, n2);
    Node *rightLCA = lca(root->right, n1, n2);
    
    if (leftLCA && rightLCA) {
        return root;
    }
   
    return (leftLCA != NULL)? leftLCA : rightLCA;
}


int main() {
    Node *root = newNode(1);
    root->left = newNode(20);
    root->right = newNode(21);
    root->right->left = newNode(30);
    root->right->right = newNode(31);
    root->right->right->left = newNode(40);
    root->right->right->left->right = newNode(51);
    
    Node *key = NULL;

    cout<<"The lowest common ancestors of 20 and 30 are: "<<endl;
    key = lca(root, 20, 30);
    cout<<(key->info);
    cout<<endl;
    
    cout<<"The lowest common ancestors of 40 and 51 are: "<<endl;
    key = lca(root, 40, 51);
    cout<<(key->info);
    cout<<endl;

    return 0;
}

Output

The lowest common ancestors of 20 and 30 are: 
1
The lowest common ancestors of 40 and 51 are: 
40

Time complexity of the above solution is O(n), where n is the number of nodes in tree. This is because it’s a simple tree traversal.

Here’s a working example:

https://ideone.com/DjhEmS

Leave a Reply

Your email address will not be published.