Lowest Common Ancestor of a Binary Search Tree medium

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q 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).”

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,null,null,null,null,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Steps and Explanation

The key to solving this problem efficiently lies in leveraging the properties of a Binary Search Tree. In a BST, the left subtree contains nodes with values smaller than the current node, and the right subtree contains nodes with values larger than the current node.

We can use a recursive approach. For each node we encounter:

1. Base Case: If the current node is null, we've reached the end of a branch and haven't found either p or q, so we return null.

2. Found Both: If the current node's value is equal to either p or q, and we've already found the other node (either directly or indirectly through recursive calls), then the current node is an ancestor of both p and q. Since we're looking for the lowest common ancestor, we can return the current node immediately.

3. One Node Found: If the current node's value is equal to either p or q, but not both, we continue searching recursively. We only need to search one subtree because if one of the nodes is found and its value is within the range defined by the current node (i.e., the other node is not found), the other node must be found within the respective subtree in a BST.

4. Neither Node Found: If the current node's value is not equal to p or q, we recursively search the left or right subtree based on the values of p and q relative to the current node's value:

   • If both p and q are less than the current node's value, we recursively search the left subtree.
   • If both p and q are greater than the current node's value, we recursively search the right subtree.
   • If p and q are on opposite sides (one less, one greater), the current node must be their lowest common ancestor, so we return the current node.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) return root; // p and q are on different sides
        return left != null ? left : right; // p and q are on the same side
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, we might traverse the entire tree.
• Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, but in a balanced BST, H is log₂(N).