Lowest Common Ancestor in a Binary Search Tree - Part 1: Recursive Solution - Binary Search Tree

The lowest common ancestor of two given nodes in a binary tree is the node at the lowest level that has both the given nodes as descendants (where we treat a node as a descendant of itself).

An example

       6
    /     \
   2       7
  / \       \
 1   4       9
    / \     /
   3   5   8

lca(1, 5) is 2.
lca(2, 5) is 2.
lca(3, 5) is 4.
lca(1, 9) is 6.

The lowest common ancestor is essentially the last node that is in common between the paths to the two nodes. For example, the path to 1 is 6-2-1, and the path to 5 is 6-2-4-5. The last node in common among the two is 2, which indeed is the lowest common ancestor.

Here in particular, we're interested in finding the lowest common ancestor of two nodes in a binary search tree. We can take advantage of the binary search tree property (i.e. that for each node, everything in the left subtree is smaller, and everything in the right subtree is larger) to find the last node in common between the two paths. Assuming the two given nodes are actually in the tree, the idea is to start at root, and if both nodes have a value smaller than the value of root, then they must be both in the left subtree, so we recursively try to determine the lowest common ancestor in the left subtree; else if both nodes have a value larger than the value of root, then they must be both in the right subtree, so we recursively try to determine the lowest common ancestor in the right subtree; otherwise, this is where the paths start to diverge, so the current root is the lowest common ancestor. Here's a possible implementation:

Node *lca(Node *root, Node *n1, Node *n2) {
  int val = root->value;

  if (n1->value < val && n2->value < val) {
    return lca(root->left, n1, n2);
  }

  if (n1->value > val && n2->value > val) {
    return lca(root->right, n1, n2);
  }

  return root;
}

Note that we don't need to worry about root being null, because we are assuming that n1 and n2 are in the tree, so in the initial call root cannot be null, and in subsequent recursive calls it cannot be null because we move to the left or right only after we've determined that both nodes are in the left or right subtree.

Time complexity

The time complexity is O(h) (where h is the height of the tree) because in the worst case the two nodes are at the very bottom of the tree, and so there will be O(h) calls to find the lowest common ancestor (since each function call we're going one level deeper in the tree), and we're doing O(1) work in each call, which means that the total work for all the calls is O(h).

Space complexity

The space complexity is O(h) (where h is the height of the tree) because this is a function that calls itself recursively, so the call stack grows with each call, and in the worst case there will be as many calls as the height of the tree, which means that the space taken is O(h).

Video with explanation