Here we are finding the lowest common ancestor of a binary tree. Here if the root2 is in between data 1 and data2 then we found
out ancestor.
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 94 95 96 97 98 99 100 101 102 103 104 105 106 |
package tree; public class LowestCommonAncestorBinaryTree { static TreeNode root; public static void main(String[] args) { // TODO Auto-generated method stub int arr[] = {10,-10,30,8,6,9,25,60,28,78}; for(int i=0; i<arr.length;i++) { insertInBST(arr[i]); } printBST(root); TreeNode data1 = new TreeNode(28); TreeNode data2 = new TreeNode(78); TreeNode result = new TreeNode(1); result = lowestCommonAncestorBT(root, data1, data2); System.out.println("The result "+result.data); } /* * Here we are finding the lowest common ancestor of a binary tree. Here if the root2 is in between data 1 and data2 then we found * out ancestor. */ private static TreeNode lowestCommonAncestorBT(TreeNode root2, TreeNode data1, TreeNode data2) { if(root2 == null) { return null; } if(root2.data == data1.data || root2.data == data2.data) { return root2; } TreeNode left = lowestCommonAncestorBT(root2.left, data1, data2); TreeNode right = lowestCommonAncestorBT(root2.right, data1, data2); if(left != null && right != null) { return root2; } if(left == null && right == null) { return null; } return left != null ? left : right; } // Here we are printing the data from the root private static void printBST(TreeNode root2) { if(root2 != null) { printBST(root2.left); System.out.println(root2.data); printBST(root2.right); } } // Here we are inserting the data in the tree node private static void insertInBST(int data) { TreeNode newNode = new TreeNode(data); if(root == null) { root = newNode; return; } TreeNode current = root; TreeNode parent = null; while(true) { parent = current; if(data < current.data) { current = current.left; if(current == null) { parent.left = newNode; return; } } else { current = current.right; if(current == null) { parent.right = newNode; return; } } } } } |
Result: 30