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

The Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST) is the deepest node that is a common ancestor of both nodes. Imagine a family tree: if you’re finding the closest shared ancestor if two people, you trace both their paths back to the nearest point where their family lines meet. In a BST, the structure of the tree helps in making this search efficient because nodes in the left subtree are always smaller than the root, and nodes in the right subtree are always larger.

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.