Created
November 9, 2012 03:00
-
-
Save zac-xin/4043437 to your computer and use it in GitHub Desktop.
Find LCA in BST
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * 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