Skip to content

Instantly share code, notes, and snippets.

@zac-xin
Created November 9, 2012 03:00
Show Gist options
  • Save zac-xin/4043437 to your computer and use it in GitHub Desktop.
Save zac-xin/4043437 to your computer and use it in GitHub Desktop.
Find LCA in BST
/*
* find lowest common ancestor in a Binary Search Tree(BST)
*/
package Chapter4;
public class FindLCA_1 {
public static void main(String args[]){
TreeNode n1 = new TreeNode(1, null, null);
TreeNode n2 = new TreeNode(2, n1, null);
TreeNode n4 = new TreeNode(4, null, null);
TreeNode n6 = new TreeNode(6, null, null);
TreeNode n5 = new TreeNode(5, n4, n6);
TreeNode n3 = new TreeNode(3, n2, n5);
TreeNode n11 = new TreeNode(11, null, null);
TreeNode n10 = new TreeNode(10, null, n11);
TreeNode n8 = new TreeNode(8, null, null);
TreeNode n9 = new TreeNode(9, n8, n10);
TreeNode n7 = new TreeNode(7, n3, n9);
TreeNode p = new TreeNode(8);
TreeNode q = new TreeNode(2);
System.out.println(findLCA_BST(n7, p, q));
}
public static TreeNode findLCA_BST(TreeNode root, TreeNode p, TreeNode q){
if(root == null)
return null;
if(root.data > Math.max(p.data, q.data)){
return findLCA_BST(root.left, p, q);
}
if(root.data < Math.min(p.data, q.data)){
return findLCA_BST(root.right, p, q);
}
return root;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment