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:
Input: A binary Search Tree and two nodes n1 and n2.
Appraoch:
- Start will the root.
- If root>n1 and root>n2 then lowest common ancestor will be in left subtree.
- If root<n1 and root<n2 then lowest common ancestor will be in right subtree.
- If Step 2 and Step 3 is false then we are at the root which is lowest common ancestor, return it.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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