Lowest Common Ancestor of BST

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

 

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

Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. But how about LCA of nodes 2 and 4? Should it be 6 or 2?

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes vand 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).” Since a node can be a descendant of itself, the LCA of 2 and 4 should be 2, according to this definition.

Hint:
A top-down walk from the root of the tree is enough.

Solution:
There’s only three cases you need to consider.

1. Both nodes are to the left of the tree.
2. Both nodes are to the right of the tree.
3. One node is on the left while the other is on the right.

For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.

Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.

A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add case number 4):

4. When the current node equals to either of the two nodes, this node must be the LCA too.

The run time complexity is O(h), where h is the height of the BST. Translating this idea to code is straightforward (Note that we handle case 3) and 4) in the else statement to save us some extra typing ):

/* Function to find LCA of n1 and n2. The function assumes that both
   n1 and n2 are present in BST */
struct node* LCA(struct node* root, int n1, int n2) {
    if (root == NULL) return NULL;
 
    // If both n1 and n2 are smaller than root, then LCA lies in left
    if (root->data > n1 && root->data > n2)
        return LCA(root->left, n1, n2);
 
    // If both n1 and n2 are greater than root, then LCA lies in right
    if (root->data < n1 && root->data < n2)
        return LCA(root->right, n1, n2);
 
    return root;
}

You should realize quickly that the above code contains tail recursion. 

Time complexity of above solution is O(h) where h is height of tree. Also, the above solution requires O(h) extra space in function call stack for recursive function calls. We can avoid extra space using iterative solution.

struct node* LCA(struct node* root, int n1, int n2) {
    while (root != NULL) {
         // If both n1 and n2 are smaller than root, then LCA lies in left
        if (root->data > n1 && root->data > n2)
           root = root->left;
 
        // If both n1 and n2 are greater than root, then LCA lies in right
        else if (root->data < n1 && root->data < n2)
           root = root->right;
 
        else break;
    }
    return root;
}

Reference:

http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html