Lowest Common Ancestor of a Binary Search Tree

Problem Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. The lowest common ancestor is defined as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Key Insights

• The LCA of two nodes p and q in a BST can be found by leveraging the properties of the BST.
• If both p and q are less than a node, then LCA lies in the left subtree of that node.
• If both p and q are greater than a node, then LCA lies in the right subtree of that node.
• If one of the nodes is on the left and the other is on the right, that node is the LCA.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree. In the worst case, this can be O(n) for a skewed tree. Space Complexity: O(1) since we are using a constant amount of space.

Solution

To find the lowest common ancestor in a binary search tree, we start at the root and traverse the tree. We compare the values of the current node with p and q:

1. If both p and q are smaller than the current node, we move to the left child.
2. If both p and q are larger than the current node, we move to the right child.
3. If one of p or q is equal to the current node or they lie on different sides, the current node is the LCA.

This approach uses a binary search tree's properties to efficiently locate the LCA.

Code Solutions