7. Lowest Common Ancestor of a Binary Search Tree

Description

Lowest Common Ancestor of a Binary 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 - Iterative

• If both the value are less then move left otherwise move right
• Think of all the scenarios not covered in the first 2 blocks that tells you the solutions
• If one is less and other is greater then that is the solutions and if either is equal then that is also
• Time: O(h) Space: O(1)

/**
 * 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) {
        TreeNode c = root;
        while (c != null) {
            if (p.val < c.val && q.val < c.val)
                c = c.left;
            else if (p.val > c.val && q.val > c.val)
                c = c.right;
            else
                return c;        
        }
        return null;
    }
}

Primary Approach: Iterative BST Search ($O(H)$ Time, $O(1)$ Space)

Intuition

Leveraging the BST property (left < root < right), we determine which subtree contains both $p$ and $q$ without needing to explore both subtrees:

1. Start at curr = root.
2. If both p.val and q.val are strictly smaller than curr.val, the LCA must lie in the left subtree $\to$ move curr = curr.left.
3. If both p.val and q.val are strictly larger than curr.val, the LCA must lie in the right subtree $\to$ move curr = curr.right.
4. If one target is on the left and the other is on the right (or curr equals $p$ or $q$), the paths split $\to$ curr is the LCA.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode curr = root;
 
        while (curr != null) {
            // Both p and q are in the left subtree
            if (p.val < curr.val && q.val < curr.val) {
                curr = curr.left;
            } 
            // Both p and q are in the right subtree
            else if (p.val > curr.val && q.val > curr.val) {
                curr = curr.right;
            } 
            // Split point found: curr is the LCA
            else {
                return curr;
            }
        }
 
        return null;
    }
}
 

Complexity

• Time Complexity: $O(H)$ — We traverse down a single path from root to target, where $H$ is the tree height ($O(\log N)$ for balanced, $O(N)$ for skewed).
• Space Complexity: $O(1)$ — Iterative traversal uses constant auxiliary space.

---

Alternative Approach: Recursive Search ($O(H)$ Time, $O(H)$ Space)

Intuition

Express the single-branch decision logic recursively:

1. If both p.val and q.val are less than root.val, recurse on root.left.
2. If both p.val and q.val are greater than root.val, recurse on root.right.
3. Otherwise, return root.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Both p and q lie in the left subtree
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
 
        // Both p and q lie in the right subtree
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
 
        // Split point found: root is the LCA
        return root;
    }
}
 

Complexity

• Time Complexity: $O(H)$ — Visits at most one node per tree level.
• Space Complexity: $O(H)$ — Call stack requires space equal to tree height $H$.

---

Key Interview Discussion Points

• BST vs. Generic Binary Tree: Point out that in a standard Binary Tree (LeetCode 236), you must search both subtrees ($O(N)$ time). For a BST, utilizing the value ordering allows pruning an entire subtree at each step, dropping time to $O(H)$ and enabling an $O(1)$ space iterative solution.
• Overflow Avoidance: Compare conditions explicitly (p.val < curr.val && q.val < curr.val) rather than using multiplication like (root.val - p.val) * (root.val - q.val) < 0, which can cause integer overflow errors on large values.

---

Easy Memory Rule

“Both values smaller? Go Left $\to$ Both values larger? Go Right $\to$ Otherwise (Split Point)? Return Current Node!”