leetcode Question: Lowest Common Ancestor of a Binary Search Tree

 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.

Analysis:

One obvious way to solve this problem is to utilizing the properties of Binary Search Tree:

• It is ordered when you do Tree traversal

However, in this post, we are solving this problem in a more general way. (It is same as the problem here).

The idea is simple: recursion.

Usually when I do recursion problem, I consider:

• What are we looking for?
• What is the termination condition?
• Which direction do we go for the searching?

According to this problem:

• We are looking for the common ancestor. In other words, if the two node are in the current node's left and right child, respectively, current node is thus the lowest common ancestor.
• When do we stop search? 1. Null node. 2. meet either one of the two nodes, the ancestor is this node or above.
• Which direction do we go ? For a binary tree, left and right.  

So, we start the search from the root node, recursively find the common ancestor for root->left and root->right, if both of them are existed, which means root is the lowest common ancestor, otherwise, the existed one is the result.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root){
            return NULL;
        }
        if (root == p || root == q){
            return root;
        }else{
            TreeNode* lc = lowestCommonAncestor(root->left, p, q);
            TreeNode* rc = lowestCommonAncestor(root->right, p, q);
            if (lc && rc){
                return root;
            }else{
                if (lc){return lc;}
                if (rc){return rc;}
            }
        }
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root == p or root == q:
            return root
        else:
            lc = self.lowestCommonAncestor(root.left, p, q)
            rc = self.lowestCommonAncestor(root.right, p, q)
            if lc and rc:
                return root
            else:
                if lc:
                    return lc
                if rc:
                    return rc