Lowest Common Ancestor

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param root: The root of the binary search tree.
15      * @param A and B: two nodes in a Binary.
16      * @return: Return the least common ancestor(LCA) of the two nodes.
17      */
18 
19     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
20         // write your code here
21         if (contains(root.left, A) && contains(root.left, B)) return lowestCommonAncestor(root.left, A, B);
22         if (contains(root.right, A) && contains(root.right, B)) return lowestCommonAncestor(root.right, A, B);
23         return root;
24         
25     }
26     
27     public boolean contains(TreeNode root, TreeNode node) {
28         if (root == null) return false;
29         if (root == node) {
30             return true;
31         } else {
32             return contains(root.left, node) || contains(root.right, node);
33         }
34     }
35 }