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.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Solution: bottom-up

Definition: The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. 

The parent would then test its left and right subtree if each contain one of the two nodes. 

If yes, then the parent must be the LCA and we pass its parent up to the root. 

If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either A or B), or NULL (if both the left and right subtree does not contain either A or B) up.

Complexity is O(n).

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if(root == null) {
            return null;
        }
        
        if(root == A || root == B) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        
        if(left != null && right != null) {  // if A and B are on both sides
            return root;
        }
        
        if(left != null) {  // either one of A,B is on one side OR A,B is not in L&R subtrees
            return left;
        }else {
            return right;
        }
    }
}

Reference: http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
如果有parent pointers的话，方法请戳链接http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html