@@ -0,0 +1,1619 @@
+package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;%0A%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;%0A%0A/**%0A * Created by sundas on 6/11/2018.%0A */%0Apublic class LowestCommonAncestorOfABinarySearchTree %7B%0A%0A  /*%0A  Lowest common ancestor of a binary search tree%0A   */%0A%0A  /**%0A   *%0A   * @param root%0A   * @return%0A   */%0A  public static BinaryTreeNode findLCABST(BinaryTreeNode root,int a,int b)%7B%0A    if(root == null)%7B%0A      return null;%0A    %7D%0A    /*%0A    Both nodes are on left root%0A     */%0A    if(root.data %3E a && root.data %3E b)%7B%0A      return findLCABST(root.left,a,b);%0A    %7D%0A    /*%0A    Both nodes are on right of root%0A     */%0A    if(root.data %3C a && root.data %3C b)%7B%0A      return findLCABST(root.right,a,b);%0A    %7D%0A    /*%0A    either: either  a or b are on either side of root%0A    or: a or b is the ancestor%0A     */%0A    else%7B%0A      return root;%0A    %7D%0A  %7D%0A%0A%0A  /**%0A   *%0A   * @param args%0A   */%0A  public static void main(String%5B%5D args) %7B%0A    BinaryTreeNode root = TreeUtils.createBST();%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22#################%22);%0A    System.out.println(findLCABST(root,3,11).data);%0A    System.out.println(findLCABST(root,5,9).data);%0A    System.out.println(findLCABST(root,4,6).data);%0A    System.out.println(findLCABST(root,9,10).data);%0A    System.out.println(findLCABST(root,6,8).data);%0A    System.out.println(findLCABST(root,4,11).data);%0A    System.out.println(findLCABST(root,7,11).data);%0A    System.out.println(findLCABST(root,10,11).data);%0A    System.out.println(findLCABST(root,8,11).data);%0A  %7D%0A%0A%7D%0A

Find lowest common ancestor in BST. O(logn)