Home » Interview coding problems/challenges

# Lowest Common Ancestor in a BST

In this article, we are going to see **how to find lowest common ancestor in a BST**? This is a very common problem that has been featured in interview rounds of Amazon, Microsoft and Synopsis.

Submitted by Radib Kar, on February 26, 2019

**Problem statement:**

**Given a Binary Search Tree and 2 nodes value n1 and n2, your task is to find the lowest common ancestor of the two nodes. Assume that n1 and n2 both existing node value of the tree.**

**Example:**

Input BST:8 / \ 4 10 / \ / \ 3 5 9 11 n1: 9 n2: 11Output:10n1: 4 n2: 10Output:8

**Solution**

The key idea of the solution is while traversing BST from root to bottom, the first node that is encountered with a value between n1 and n2, i.e., n1<node->data<n2, is the **Least Common Ancestor(LCA)** of those two nodes having values n1, n2 respectively.

So, traverse the BST using pre-order traversal. If we find a node with value in between n1 and n2, the node is the LCA. If its (the currently processed node) value is greater than both n1 and n2, then the LCA lies in the left subtree of the currently processed node and if its (the currently processed node) value is smaller than both n1 and n2 then the LCA must be on the right subtree of the currently processed node.

**Algorithm:**

FUNCTION LCA(root, n1, n2)While (true) //if root->data lies between n1 and n2 both IF ((root->data>=n1 && root->data<=n2)||(root->data<=n1 && root->data>=n2)) return root; //LCA found IF(n1data) //root->data > both n1 & n2 root=root->left; //go to left Else//root->data < both n1 and n2 root=root->right; //go to right END While END FUNCTION

**Example with explanation:**

Input BST:8 / \ 4 10 / \ / \ 3 5 9 11 n1: 9 n2: 11 Nodes are represented by their respective values In main we call LCA (8,9,11) LCA(8,9,11) root->data<n1 //8<9 ensures root->data smaller than both n1 & n2 root=root->right LCA(10,9,11) root->data>n1&& root->data<n2 //10>9&& 10<11 ensures root->data in between n1 & n2 return root//10 Program terminates.. 10 is LCA

**C++ implementation**

#include <bits/stdc++.h> using namespace std; class Node{ public: int data; //value Node *left; //pointer to left child Node *right; //pointer to right child }; // creating new node Node* newnode(int data) { Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } Node* LCA(Node *root, int n1, int n2) { while(true){ if((root->data>=n1 && root->data<=n2)||(root->data<=n1 && root->data>=n2)) return root; if(n1<root->data) root=root->left; else root=root->right; } } int main(){ cout<<"tree is built as per 1st example\n"; Node *root=newnode(8); root->left= newnode(4); root->right= newnode(10); root->right->right=newnode(11); root->right->left=newnode(9); root->left->left=newnode(3); root->left->right=newnode(5); int n1=9, n2=11; cout<<"Lowest common ancestor of "<<n1<<" & "<<n2; cout<<" is:"<<LCA(root,n1,n2)->data<<endl; return 0; }

**Output**

tree is built as per 1st example Lowest common ancestor of 9 & 11 is:10

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL