Leetcode 235: Lowest common ancestor in binary search tree

April 25, 2016

Study the code:

https://github.com/douglasleer/LeetCode-Java-Solutions/blob/master/235.lowest-common-ancestor-of-a-binary-search-tree.java

Walk through less than 10 lines of code, and then add some comment:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p.val > q.val) return lowestCommonAncestor(root, q, p);   // Julia, reduce 2 cases to 1 case: p.val <= q.val

if (q.val < root.val) return lowestCommonAncestor(root.left, p, q); // two nodes are in the left side of root

if (p.val > root.val) return lowestCommonAncestor(root.right, p, q); // two nodes are in the right side of root

return root;   // otherwise, one node is left side, another node is right side: root is the parent.

}