Lowest Common Ancestor in a Binary Search Tree - Part 3: Handling Invalid Nodes - Binary Search Tree

In the solutions shown in part 1 and 2, we've assumed that the two given nodes were in the binary search tree. Let's consider the case where we cannot make that assumption. This means that any of the two given nodes can be null, or not present in the tree. We can easily handle these cases by first checking for null nodes, and then making sure that they are both in our tree:

Node *lca(Node *root, Node *n1, Node *n2) {
  if (n1 == nullptr || n2 == nullptr) return nullptr;

  n1Found = findNodeInBST(root, n1->value);
  if (n1Found != n1) return nullptr;

  n2Found = findNodeInBST(root, n2->value);
  if (n2Found != n2) return nullptr;

  return lcaSolution2(root, n1, n2); // or lcaSolution1
}

Where findNodeInBST is a function that finds the node with the given value in a binary search tree, and returns it, or returns null if there is no such node (See Find Node in a Binary Search Tree for more detail). We check that what it returns is equal to the node we are given, i.e. it is not null or some other node.

If all the checks pass, we call either the recursive solution to find the lowest common ancestor we've seen in part 1 (lcaSolution1), or the iterative solution we've seen in part 2 (lcaSolution2).

Time complexity

The time complexity is still O(h) (where h is the height of the tree) because both findNodeInBST and lcaSolution1 (or lcaSolution2) run in O(h) time.

Space complexity

The space complexity is O(h) if we use the recursive version of findNodeInBST or lcaSolution1. On the other hand, if we use the iterative version of findNodeInBST and lcaSolution2, the space complexity is O(1).

Video with explanation