Blind 75Easy

Lowest Common Ancestor in BST — Guided Descent

Leverage BST ordering: move left or right until the current node splits the two targets.

TreeBinary Search Tree

View problem on LeetCode

Problem Statement

Given a binary search tree and two nodes p and q, return their lowest common ancestor.

Why This Problem Matters

Demonstrates how BST properties simplify search problems.
Foundation for LCA problems in general graphs and binary trees.
Encourages reasoning about orderings and branching.

Thought Process

Compare node values

If both p and q are less than current node, move left; if both greater, move right.

Identify split point

When current node lies between p and q (inclusive), it is the LCA.

Iterative vs recursive

Iterative loop avoids recursion but logic remains identical.

Step-by-Step Reasoning

Set current = root.
While true, if p and q less than current.val set current = current.left.
Else if both greater move to current.right.
Otherwise break and return current.

Dry Run

BST root 6 with nodes 2 and 8

Split occurs immediately at root; LCA = 6.

Nodes 2 and 4 in left subtree

Traverse left to node 2 then move right to 4; LCA = 2 after split condition.

Complexity Analysis

Time

O(h)

Space

O(1)

Why

Traverse path from root to LCA; h is tree height.

Annotated Solution

JAVA

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

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

The LCA is the first node where the targets diverge in direction relative to the BST ordering.

Common Pitfalls

Treating as general binary tree without using ordering leads to more complex recursion.
Not handling case where p equals q or equals root; split condition still holds.
Null checks missing for degenerate trees; ensure root non-null per constraints.

Follow-Up Questions

How do you handle LCA in a general binary tree? (Use parent pointers or recursion returning matches.)
What about repeated queries? (Preprocess with binary lifting.)

Key Takeaways

Exploit BST properties whenever available to simplify logic.

Iterative traversal avoids recursion overhead.

General LCA problems require more complex structures—mention them as follow-ups.