Binary Search Trees: LCA in a BST

Problem Statement:

You are given a BST root node and 2 node values n1 and n2, you need to find the Lowest Common Ancestor.

Solution

As we know the property of BST,

check if the current node is less than both n1 and n2 then LCA lies in the right subtree. Then call the recursive function for the right subtree.

check if the current node is greater than both n1 and n2 then LCA lies in the left subtree. Then call the recursive function for the left subtree.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;


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


Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int key)
{
    if (node == NULL) return get_new_node(key);
    if (key < node->data)
        node->left  = insert_into_bst(node->left, key);
    else
        node->right = insert_into_bst(node->right, key);
    return node;
}

Node* get_lca(Node* root, int n1, int n2)
{
    if (root == NULL) return NULL;
  
    if (root->data > n1 && root->data > n2)
        return get_lca(root->left, n1, n2);
  
    if (root->data < n1 && root->data < n2)
        return get_lca(root->right, n1, n2);
  
    return root;
}
  

int main()
{
    int key = 6; 
 
   /* 
              5
           /     \
          3       7
         /  \    /  \
         2   4   6   8  */
    Node *root = NULL;
    root = insert_into_bst(root, 5);
    insert_into_bst(root, 3);
    insert_into_bst(root, 2);
    insert_into_bst(root, 4);
    insert_into_bst(root, 7);
    insert_into_bst(root, 6);
    insert_into_bst(root, 8);
 
    int n1 = 6, n2 = 8;
    Node *t = get_lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->data);
  

    return 0;
}

Output:

LCA of 6 and 8 is 7