Lowest Common Ancestor of a Binary Search Tree

题目：

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Analysis

This problem can be solved by using BST property, i.e., left < parent < right for each node. There are 3 cases to handle.

 1     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) 
 2     {
 3         TreeNode m = root;
 4         
 5         if(m.val>p.val&&m.val<q.val) return m;
 6         if(m.val>p.val&&m.val>q.val)
 7         {
 8             return lowestCommonAncestor(root.left,p,q);
 9         }
10         if(m.val<p.val&&m.val<q.val)
11         {
12             return lowestCommonAncestor(root.right,p,q);
13         }
14         
15         return root;
16     }

reference：http://www.programcreek.com/2014/07/leetcode-lowest-common-ancestor-of-a-binary-search-tree-java/