Lowest Common Ancestor of a Binary Search Tree – 235. LeetCode

Imagine you’re navigating a family tree and need to find the closest common ancestor of two family members. The Lowest Common Ancestor (LCA) in a Binary Search Tree (BST) is the “earliest” node in the tree that is an ancestor of two given nodes. This concept is useful in systems like hierarchical file structures or organizational charts.

In a BST, all values to the left of a node are smaller, and all values to the right are larger. This property makes finding the LCA efficient compared to a general binary tree.

Brute Force Approach

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;

    if (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;

    return (left != null) ? left : right;
}

• This approach checks every node to find  p  and  q , traversing both left and right subtrees recursively.

• The LCA is identified when both nodes are found in different subtrees of the current root.

Optimized Approach: Recursive Search in BST

The divide-and-conquer pattern is used, where the problem is broken into subproblems at each recursive step.

The optimized approach leverages the BST properties:

1. If both nodes are smaller than the root, the LCA must be in the left subtree.

2. If both nodes are larger than the root, the LCA must be in the right subtree.

3. If the nodes split (one smaller and one larger, or one matches the root), the current root is the LCA.

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // While we haven't found the LCA
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                // Both nodes are smaller, move to the left subtree
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                // Both nodes are larger, move to the right subtree
                root = root.right;
            } else {
                // Nodes split, current root is the LCA
                return root;
            }
        }
        return null;
    }
}

Line-By-Line Explanation

Step 1: Start of While Loop

while (root != null)

• Initiates a loop to traverse the BST starting from the root node. The loop continues as long as the root is not null.

Step 2: Left Subtree Check

if (p.val < root.val && q.val < root.val) {
    root = root.left;
}

• If both nodes are smaller than the current node, the LCA must lie in the left subtree because of the BST property:

• All values in the left subtree are smaller than the root’s value.

4. Right Subtree Check

else if (p.val > root.val && q.val > root.val) {
    root = root.right;
}

5. Nodes Split (LCA Found)

else {
    return root;
}

• Executes when p and q are on different sides of the current node (one is smaller and the other is larger), or when one of them matches the current node.

6. Return

return null;

• Provides a fallback return value in case the tree is empty (root == null).

Why This Code Works

This code works because it leverages the Binary Search Tree (BST) property, which ensures that all nodes in the left subtree are smaller than the root and all nodes in the right subtree are larger. By comparing the values of p and q with the current node (root), the code efficiently determines whether to move left, move right, or stop when the nodes split (i.e., one is on each side of the root or one matches the root). The algorithm iteratively traverses the tree, ensuring O(h) time complexity, where h is the height of the tree, and O(1) space complexity since no recursion stack is used.