Question :
WAP to find the lowest common ancestor of two given nodes a binary search Tree.
Let T1 be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T1 that has both n1 and n2 as descendants.
In the above Tree ,LowestCommonAncestor(LCA) of Node 4 and Node 7 in BST is Node 6.Similary LowestCommonAncestor of Node 1 and Node 14 in BST is Node 8
Algorithm :
The problem is solved in recursive way.
Step 1 : If the node is null ,return null.
Step 2 : If both data1 and data2 are equal to root ,then return root.data1 and data2 are two node values for which we are finding LCA.
Step 3 : If both data1 and data2 are equal to root ,then traverse left sub tree, as LCA lies in left sub tree.
Step 4 : If both data1 and data2 are equal to root ,then traverse right sub tree, as LCA lies in right sub tree.
Program :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
package com.ai1tutorial.dsalgo.bst; class BinarySearchTree { int data; BinarySearchTree left; BinarySearchTree right; public BinarySearchTree(int data) { super(); this.data = data; this.left = null; this.right = null; } } public class LowestCommonAncestor { public static void main(String[] args) { BinarySearchTree root = newNode(8); insert(root, 3); insert(root, 10); insert(root, 1); insert(root, 6); insert(root, 14); insert(root, 4); insert(root, 7); insert(root, 13); System.out .println("LowestCommonAncestor of Node 4 and Node 7 in BST is Node " + lowestCommonAncestor(root, 4, 7).data); System.out .println("LowestCommonAncestor of Node 1 and Node 14 in BST is Node " + lowestCommonAncestor(root, 1, 14).data); } private static BinarySearchTree newNode(int data) { BinarySearchTree node = new BinarySearchTree(data); node.left = node.right = null; return node; } private static BinarySearchTree insert(BinarySearchTree node, int data) { if (null == node) { return (newNode(data)); } else { if (data <= node.data) { node.left = insert(node.left, data); } else { node.right = insert(node.right, data); } return node; } } private static BinarySearchTree lowestCommonAncestor(BinarySearchTree root, int data1, int data2) { if (null == root) { return null; } while (null != root) { // If both data1 and data2 are smaller than root, then LCA lies in //left if (root.data > data1 && root.data > data2) { root = root.left; } // If both data1 and data2 are greater than root, then LCA lies in // right else if (root.data< data1 && root.data < data2) { root = root.right; } else break; } return root; } private static BinarySearchTree lowestCommonAncestorLCA( BinarySearchTree root, int firstElement, int secondElement) { if (null == root) { return null; } while (null != root) { // If both firstElement and secondElement are smaller than root, // then LCA lies in // left if (root.data > firstElement && root.data > secondElement) { root = root.left; } else if (root.data < firstElement && root.data < secondElement) { // If // both // firstElement // and secondElement are // greater than // root, // then LCA lies // in right root = root.right; } else { break; } } return root; } } |
|
1 2 3 4 5 |
OutPut : LowestCommonAncestor of Node 4 and Node 7 in BST is Node 6 LowestCommonAncestor of Node 1 and Node 14 in BST is Node 8 |