BST structure tells you where the ancestor lives before you even start searching

The problem gives you a BST and two nodes p and q that both exist in it. Find their lowest common ancestor — the deepest node that has both as descendants, where a node counts as a descendant of itself.

The definition of LCA is the same for any binary tree, but the BST structure changes everything about how you find it. In a plain binary tree, you have no choice but to search both subtrees. In a BST, the ordering invariant — every node in the left subtree is smaller, every node in the right subtree is larger — lets you navigate rather than search.

The BST used in both examples. For p=2, q=8: at node 6, one target is left and one is right — split point found immediately. For p=2, q=4: both are left of 6, walk left; at node 2, p itself is the root — node 2 is the LCA.

The problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is defined as the deepest node that has both p and q as descendants, where a node is allowed to be a descendant of itself. Full statement: LeetCode 235.

Constraints:
- The number of nodes in the tree is in the range [2, 10^5].
- -10^9 <= Node.val <= 10^9
- All Node.val are unique.
- p != q
- p and q will exist in the BST.

What the constraints force

Nodes: [2, 10^5]. Values: [-10^9, 10^9], all unique. Both p and q are guaranteed to exist.

The node count allows O(N) solutions — 10^5 nodes with a simple traversal is fine on time. But the word "unique" is what unlocks the BST approach: because no two nodes share a value, comparison is unambiguous. You never have to worry about which of two nodes valued 4 you are looking at.

The guarantee that p and q both exist means you never need to handle the "target not found" case. The iterative loop can return None on paper, but in practice the constraints say that line is unreachable.

p != q rules out a degenerate case where both targets are the same node. The LCA in that case would be p itself, but the problem says this never happens.

The value range [-10^9, 10^9] means values can be negative. The BST comparison still works fine — you are comparing actual values, not array indices or non-negative counts.

Approach 1: brute-force DFS on the binary tree

Before reaching for the BST property, it is worth understanding what the general binary tree solution does. This runs on any binary tree, not just a BST.

The logic: for each node, check whether p and q are in different subtrees (which makes the current node the LCA) or in the same subtree (recurse toward that subtree). The base case handles finding p or q directly — when you hit one of the targets, return it upward; if both subtrees returned non-null results, the current node is the split point.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
 
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
 
        if left and right:
            return root
 
        return left if left else right

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || 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;
    }
}

The base case root == p || root == q handles the situation where one of the targets is itself an ancestor of the other. When we find p, we return it without looking further. If q is in p's subtree, the right side of the recursion will find nothing and return null — so left gets p and right gets null, and we return p. The LCA is correct.

Hand trace: p=2, q=8 on the example BST

lowestCommonAncestor(root=6, p=2, q=8)
  root != p, root != q, recurse both sides

  lowestCommonAncestor(root=2, p=2, q=8)
    root == p -> return node(2)   [left result]

  lowestCommonAncestor(root=8, p=2, q=8)
    root == q -> return node(8)   [right result]

  left=node(2), right=node(8), both non-null -> return root=node(6)

Answer: 6  (correct)

The algorithm visits root 6, then both subtrees. It found both targets in different subtrees, so 6 is the LCA. It visited 3 nodes out of 9 in this case, but in the worst case it must visit all N nodes.

Complexity for the brute-force approach

Time: O(N). In the worst case — a skewed tree, or both targets deep in the same subtree — you visit every node before finding the answer. There is no way to skip subtrees without additional information.

Space: O(H) for the call stack. H is the tree height: O(log N) for a balanced tree, O(N) for a fully skewed one.

This is correct. It is also wasteful on a BST, because it ignores the structure completely.

Approach 2: using the BST property to navigate directly

The BST invariant tells you exactly where each value lives relative to any node. If both p.val and q.val are smaller than current.val, both nodes are in the left subtree — go left. If both are larger, go right. The moment they are on different sides (or one of them equals the current node), you are at the LCA.

There is no search here. You are navigating. The ordering invariant does all the work.

Iterative version

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        p_val = p.val
        q_val = q.val
 
        current = root
 
        while current:
            current_val = current.val
 
            if p_val < current_val and q_val < current_val:
                current = current.left
            elif p_val > current_val and q_val > current_val:
                current = current.right
            else:
                return current
 
        return None  # unreachable given the constraints

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pVal = p.val;
        int qVal = q.val;
 
        TreeNode current = root;
 
        while (current != null) {
            int currentVal = current.val;
 
            if (pVal < currentVal && qVal < currentVal) {
                current = current.left;
            }
            else if (pVal > currentVal && qVal > currentVal) {
                current = current.right;
            }
            else {
                return current;
            }
        }
 
        return null; // unreachable given the constraints
    }
}

The else branch covers three distinct situations, all of which correctly identify the LCA:

• p.val < current.val and q.val > current.val (or vice versa): they are on opposite sides
• p.val == current.val: p is the current node, and since both p and q are in the subtree rooted at p, p is the LCA
• q.val == current.val: same reasoning with q

All three collapse into one branch because the math works out: if neither "both left" nor "both right" is true, you are at the split point.

Recursive version

The same logic written recursively — shorter, but uses O(H) stack space:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

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

The recursive version is cleaner to read. The iterative version is O(1) space and avoids stack growth for deep trees. For n = 10^5 with a fully skewed BST, that is 100,000 stack frames with the recursive approach — worth considering, though Python's recursion limit would be the first problem.

Hand trace: p=2, q=4 on the example BST

current = 6, p_val=2, q_val=4
  both < 6 -> go left

current = 2, p_val=2, q_val=4
  p_val == current_val (2 == 2)
  -> neither "both left" nor "both right" -> return node(2)

Answer: 2  (correct, because p=2 is an ancestor of q=4)

Two steps. The brute-force version would also have visited node 4 (to confirm it exists in the subtree) before returning. Here, the moment we hit p itself, the comparison logic terminates.

Complexity for the BST approach

Time: O(H) where H is the tree height. At each step you move one level deeper. For a balanced BST, H = O(log N). For a fully skewed BST, H = O(N). The problem does not guarantee balance, so you can say O(H) and note the balanced/skewed cases separately.

Space: O(1) for the iterative version — only the current pointer. O(H) for the recursive version, due to the call stack.

Edge cases

One target is the ancestor of the other (Example 2, p=2, q=4): the iterative loop returns as soon as current.val equals either p_val or q_val. In the brute-force version, returning the found node immediately and letting the null from the other side combine with it is what handles this. Both versions are correct for this case by design.

Root is the LCA (p=2, q=8 in the example): the very first comparison in the iterative approach hits the else branch on the root. One comparison, done. The brute-force version recurses into both children, discovers the result, and then returns on the way back up — it visits three nodes minimum.

Tree has only two nodes ([2,1], p=2, q=1): root is 2, p is 2, q is 1. In the iterative BST approach: p_val == current_val, so neither "both left" nor "both right", return root = node(2). In the brute-force: root == p, return root immediately. Both return 2. Correct.

Deeply skewed BST (a chain of N nodes, p and q near the bottom): both approaches walk the whole chain. The BST approach is O(N) here. The brute-force is also O(N) but visits more nodes because it has to confirm both sides. In the worst skewed case, the BST iterative still uses O(1) space while the brute-force uses O(N) stack space.

Negative values: the comparison operators < and > work correctly for negatives. A BST with values [-3, -5, -2] where root is -3, p=-5, q=-2 returns -3 immediately on the first step (one is left, one is right). No special handling needed.

Comparison table

H = O(log N) for balanced trees, O(N) for skewed ones.

Which version I would ship

The iterative BST approach. The reasoning is simple enough to state in one sentence: both targets cannot be in the same subtree if the current node's value is strictly between them or equal to one of them. That sentence is the entire algorithm. The code is seven lines in Python, and every line corresponds directly to a branch of that sentence.

I would not ship the recursive BST version in production code for a system that might encounter pathologically skewed trees. The O(1) space of the iterative version is genuinely better when you cannot guarantee balance. For a coding interview, either is fine — I would mention the space difference explicitly.

The brute-force approach is the answer to a different question: "how do you find the LCA in a binary tree without any ordering invariant?" That is problem 236. It is worth keeping in your head as a fallback — when the problem says "binary tree" rather than "BST", you cannot navigate; you have to search. The constraint "BST" is what makes navigation possible here.

The underlying pattern: navigation vs. search in ordered structures

The BST LCA problem is an instance of a general pattern: when the data structure provides an ordering guarantee, you can replace search (visit until found) with navigation (reason about where the target must be and walk there). Binary search in an array does the same thing. The BST search itself does the same thing. Here you are navigating toward the split point rather than toward a single target.

The key recognition: the LCA is the first node where p and q stop being on the same side. In an unordered tree you cannot identify "same side" without visiting both sides. In a BST you can. That is the whole insight.

Where this fits and what comes next

In the trees series, this problem follows Validate Binary Search Tree (98) and Kth Smallest Element in a BST (230). Those two established that the BST invariant — left subtree smaller, right subtree larger — is something you reason about, not just something you use to make searches fast. LCA 235 is the application: you use the invariant to navigate rather than search.

Lowest Common Ancestor of a Binary Tree (236) is the natural companion. It is the same problem statement with the word "BST" replaced by "binary tree." The navigation trick disappears entirely; you fall back to the brute-force DFS. The comparison between 235 and 236 is the clearest possible demonstration of what BST structure buys you.

Delete Node in a BST (450) applies the same navigation pattern. You walk the tree using BST comparisons to locate the target, then restructure the subtree around it. The walk-to-target part is identical to what you do here.

Kth Smallest Element in a BST (230) also navigates using the ordering but uses in-order traversal rather than comparison-based routing. The contrast is interesting: in LCA you use < and > to route, in Kth Smallest you use in-order count.

Insert into a BST (701) is the simplest application: navigate to the null position where the new node belongs, insert. One BST comparison per level, same O(H) time, and it builds intuition for why the iterative pattern is natural for BST traversal.