Least Common Ancestor

You are given a Binary Tree and two nodes N1 and N2, you need to return the least common ancestor of N1 and N2. The lowest common ancestor between two nodes N1 and N2 is defined as the lowest node in the tree that has both N1 and N2 as its descendants where we allow a particular node to be a descendant of itself.

In the tree above, the lowest common ancestor of 4 and 14 is 8, since the lowest node in the tree that has both 4 and 14 as its descendants is 8. The lowest common ancestor of 3 and 7 is 3 itself.

Algorithm

The idea is to traverse the tree starting from the root. If any of the given nodes (N1 and N2) matches with the current node, we return the current node. If it does not matches with the given nodes, we recur for left and right subtree. The idea is – the node which has one key present in its left subtree and the other key present in its right subtree is our answer. In case, both the keys lies in either of the subtrees, then that particular subtree has the LCA.

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

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

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    cout<<"The least common ancestor of 4 and 14 is: "<<findLCA(root, 4, 14)->data;
    return 0;
}

Also, check out another popular interview problem Diameter of a Binary Tree.

One comment

Leave a Reply

Your email address will not be published.