Solution: Lowest Common Ancestor of a Binary Search Tree

Statement#

Given a binary search tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, node1 and node2.

The lowest common ancestor of two nodes, node1 and node2, is defined as the lowest node in the binary search tree that has both node1 and node2 as descendants.

By definition, a node is a descendant of itself. For example, if node2 is a descendant of node1, and we know that node1 is a descendant of itself, then node1 will be the lowest common ancestor of node1 and node2.

Constraints:

• $2 \leq n \leq 500$
• $-10^3 \leq$ Node.data $\leq 10^3$
• All Node.data are unique.
• node1 $\neq$ node2
• node1 and node2 exist in the tree.

Solution#

We will use Tree depth-first search to find the LCA of two nodes in a BST. The LCA is the lowest-level node that is a common ancestor of both node1 and node2. In a BST, the nodes in the left subtree of any given node have values less than the node’s value, and the nodes in the right subtree have values greater than the node’s value. This BST property helps narrow down the search space, allowing us to identify the LCA effectively without having to explore the entire tree.

Since node1 and node2 are distinct values, and both must be present in the BST, there exist two cases where they can lie:

• If one of the nodes is in the left subtree of the current node and the other is in the right subtree, then the current node itself will be the LCA.

• If one of the nodes is an ancestor of the other node, then the parent node will be the LCA.

The steps of the algorithm above are given below:

1. Initialize current with the root node.
2. We will start traversing the BST from the root node using current. While traversing, we will compare the value of the current node with the values of node1 and node2.
   • If the value of the current node is greater than the values of both nodes, it means the LCA lies in the left subtree of the current node, since both nodes must be present in the left subtree. Therefore, search for the LCA in the left subtree.
   • If the value of the current node is smaller than the values of both nodes, it means the LCA lies in the right subtree of the current node, since both nodes must be present in the right subtree. Therefore, search for the LCA in the right subtree.
   • If the value of the current node is between the values of both nodes (inclusive), it means the current itself is the LCA. Therefore, return current as the LCA of node1 and node2.
3. Continue the traversal until we find the LCA.

Let’s look at the following illustration to get a better understanding of the solution:

Time complexity#

The time complexity of the solution is $O(n)$, where $n$ is the number of nodes in the binary search tree. This is because in the worst case, we will traverse all the nodes in the binary search tree.

Space complexity#

The space complexity of this solution is $O(1)$, since we are not using any extra space.