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:
| 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
why (root.data <= n1.data) in the els if statement rather than (root.data < n1.data)