Lowest Common Ancestor in a Binary Search Tree.

Objective: Find the Lowest Common Ancestor of two given nodes in a Binary Search Tree

What is Lowest Common Ancestor

In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.

Similar Problem: Lowest Common Ancestor in a Binary Tree ( Not Binary Search Tree).

Example:

Lowest-Common-Ancestor-BST
Lowest-Common-Ancestor-BST

Input: A binary Search Tree and two nodes n1 and n2.

Appraoch:

  1. Start will the root.
  2. If root>n1 and root>n2 then lowest common ancestor will be in left subtree.
  3. If root<n1 and root<n2 then lowest common ancestor will be in right subtree.
  4. If Step 2 and Step 3 is false then we are at the root which is lowest common ancestor, return it.
LCA-in-Binary-Search-Tree
LCA-in-Binary-Search-Tree

Complete Code:

public class LowestCommonAncestorBST {
public Node LCA(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
// If root>n1 and root>n2 then lowest common ancestor will be in left
// subtree.
if (root.data > n1.data && root.data > n2.data) {
return LCA(root.left, n1, n2);
}
// If root<n1 and root<n2 then lowest common ancestor will be in right
// subtree.
else if (root.data <= n1.data && root.data < n2.data) {
return LCA(root.right, n1, n2);
}
// if I am here that means i am at the root which is lowest common
// ancestor
return root;
}
public Node LCA2(Node root, Node n1, Node n2) {
while (root != null) {
// If root>n1 and root>n2 then lowest common ancestor will be in
// left
// subtree.
if (root.data > n1.data && root.data > n2.data) {
root = root.left;
}
// If root<n1 and root<n2 then lowest common ancestor will be in
// right
// subtree.
else if (root.data <= n1.data && root.data < n2.data) {
root = root.right;
}
// if I am here that means i am at the root which is lowest common
// ancestor
else {
return root;
}
}
return root;
}
public static void main(String[] args) throws java.lang.Exception {
Node root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
Node n1 = new Node(5);
root.left.left = n1;
root.left.right = new Node(13);
Node n2 = new Node(14);
root.left.right.right = n2;
root.left.right.left = new Node(12);
LowestCommonAncestorBST i = new LowestCommonAncestorBST();
System.out.println("Recursive-Lowest Common Ancestor of Nodes "
+ n1.data + " and " + n2.data + " is : "
+ i.LCA(root, n1, n2).data);
Node x = i.LCA2(root, n1, n2);
System.out.println("Iterative-Lowest Common Ancestor of Nodes "
+ n1.data + " and " + n2.data + " is : " + x.data);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}

Output:

Recursive-Lowest Common Ancestor of Nodes 5 and 14 is : 10
Iterative-Lowest Common Ancestor of Nodes 5 and 14 is : 10

1 thought on “Lowest Common Ancestor in a Binary Search Tree.”

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.