Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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,3,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.

Example 3:

Input: root = [2,1], p = 2, q = 1 Output: 2

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

Approach: Exploit the BST Property (Iterative Walk)

Algorithm

1. The BST property guarantees that at any node, values in the left subtree are smaller and values in the right subtree are larger
2. The LCA is the first node whose value lies between p.val and q.val inclusive, because that is where the paths to p and q diverge
3. Start at the root and loop: if both p.val and q.val are smaller than the current value, move left; if both are larger, move right
4. If the current value is between p.val and q.val (or equal to one of them), it is the LCA
5. Since p and q are guaranteed to exist in the BST, this node is always found

Time & Space Complexity

• Time Complexity: O(h) - only one root-to-node path is walked, where h is the tree height
• Space Complexity: O(1) - a single pointer is used, no recursion stack

Java Implementation

public class LowestCommonAncestorOfABinarySearchTree {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // Test method
    public static void main(String[] args) {
        TreeNode n0 = new TreeNode(0);
        TreeNode n3 = new TreeNode(3);
        TreeNode n5 = new TreeNode(5);
        TreeNode n4 = new TreeNode(4, n3, n5);
        TreeNode n2 = new TreeNode(2, n0, n4);
        TreeNode n7 = new TreeNode(7);
        TreeNode n9 = new TreeNode(9);
        TreeNode n8 = new TreeNode(8, n7, n9);
        TreeNode root = new TreeNode(6, n2, n8);

        System.out.println("LCA of 2 and 8: " + lowestCommonAncestor(root, n2, n8).val); // Expected: 6
        System.out.println("LCA of 2 and 4: " + lowestCommonAncestor(root, n2, n4).val); // Expected: 2
    }
}

Recursive Implementation

public TreeNode lowestCommonAncestorRecursive(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestorRecursive(root.left, p, q);
    }
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestorRecursive(root.right, p, q);
    }
    return root;
}

Example Walkthrough

For root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8:

1. Start at 6. p.val = 2 < 6 and q.val = 8 > 6: the values split on either side, so 6 is the LCA
2. For p = 2, q = 4: start at 6, both are < 6, move left to 2
3. At 2, p.val = 2 equals the current value, so 2 is the LCA (a node can be a descendant of itself)

Key Points

1. Split Point: The LCA is the first node whose value falls between the two given values
2. BST Property: Comparisons against the current node decide whether to go left, right, or stop
3. O(h) Time: Only one downward path is traversed, unlike the O(n) general-binary-tree approach
4. O(1) Space: The iterative version needs no stack
5. Node Self-Descendant: Equality with one of p or q correctly stops the search