Find Lowest Common Ancestor in Binary Search Tree

A common algorithm concerning binary search tree(BST) is finding the lowest common ancestor(LCA) of two given nodes. For example, if we have this tree, then LCA of 7 and 1 is 5. Or, the LCA of 0 and 1 is 2. So how can we do this? There are two ways to do this. We can use recursive or iterative algorithms.

For the recursive algorithm, we're going to use a convenient method to check if a node presents in a tree. That method was covered in this post "Searching for a node in a binary tree" The convenient method name is isNodeInTree(). It returns true if a node presents in a tree. Otherwise, it returns false. Next, we can recursively do the following steps for each node in a tree in order to find the LCA.

1. If the current node is null or if one of the nodes we need to find LCA for is null, we return null.
2. Next, if both nodes present in the current node's left subtree, then we call the function on the left child. The reason is that if the left child has both nodes, it is the lower common ancestor than the current node.
3. Repeat step 2 for right child node
4. In the end if neither left or right child node is the LCA, we know that the current node is the LCA

Node getLCAforNodesOfBST(Node root, Node firstNode, Node secondNode)
{
  if (root == null || firstNode == null || secondNode == null)
    return null;

  if (isNodeInTree(root.left, firstNode) && isNodeInTree(root.left, secondNode))
    getLCAforNodesOfBST(root.left, firstNode, secondNode);
  else if (isNodeInTree(root.right, firstNode) && isNodeInTree(root.right, secondNode))
    getLCAforNodesOfBST(root.right, firstNode, secondNode);
  else
    return root;
}

As you can see, the recursive method requires a lot of extra memory and steps. However, it can be used for regular binary trees, not just binary search trees. On the other hand, we can use an iterative algorithm to find LCA too. In fact, iterative method below is more efficient than recursive one because it uses less memory. However, this applies to only binary search trees

Node getLCAforNodesOfBST(Node root, Node firstNode, Node secondNode)
{
  Node currentNode = root;
 
  while (currentNode != null)
  {
    if (currentNode.data < firstNode.data && currentNode.data < secondNode.data)
     currentNode = currentNode.right;
    else if (currentNode.data > firstNode.data && currentNode.data > secondNode.data)
     currentNode = currentNode.left;
    else
     break;
  }

  return currentNode;
}

The strategy here is straight forward. We just look at the current node. If it is less than both of the nodes we're searching LCA for, we advance to the current's node right child. Why? Because this is a binary search tree! If the current node is less than both nodes, then those nodes must be on the right subtree of the current node. Moreover, we also know for sure that the current node is not the LCA.

In the next case, if the current node is greater than both of the nodes we're searching for, then the LCA must be on the left subtree of the current node. Thus, we advance to the current node's left child.

Lastly, if both of those cases aren't true, then the current node must be the LCA of the nodes we're searching LCA for.

Hope that helps :) If you have any question please put it in the comment section below. Thanks.