235. Lowest Common Ancestor of a Binary Search Tree

Quick Identifier

• Topic: trees
• Pattern: BST property (search-space shrink from ordered keys)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 235

Quick Sights

• Time Complexity: O(h) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given a BST’s root and two distinct nodes primary and secondary that exist in the tree, return their lowest common ancestor—the deepest node that has both nodes as descendants (a node can be a descendant of itself).

Concept Explanation

Given a BST’s root and two distinct nodes primary and secondary that exist in the tree, return their lowest common ancestor—the deepest node that has both nodes as descendants (a node can be a descendant of itself).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• BST + LCA together → walk from root using comparisons to p and q
• No parent pointers needed
• Values are comparable at each step

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — store paths root→p and root→q as arrays — O(h) time / O(h) space — then scan last common element.
• Better — recursive BST split — O(h) time / O(h) stack — same idea as iterative but with frames.
• Optimal — O(h) time / O(1) space — walk: if both targets smaller than current, go left; both larger, go right; otherwise current splits them or equals one → LCA.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root *TreeNode, primary *TreeNode, secondary *TreeNode) *TreeNode {
	small := primary
	large := secondary
	if primary.Val > secondary.Val {
		small = secondary
		large = primary
	}
	current := root
	for current != nil {
		if current.Val < small.Val {
			current = current.Right
			continue
		}
		if current.Val > large.Val {
			current = current.Left
			continue
		}
		return current
	}
	return nil
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function lowestCommonAncestor(root, primary, secondary) {
	let small = primary.val <= secondary.val ? primary : secondary;
	let large = primary.val <= secondary.val ? secondary : primary;
	let current = root;
	while (current !== null) {
		if (current.val < small.val) {
			current = current.right;
		} else if (current.val > large.val) {
			current = current.left;
		} else {
			return current;
		}
	}
	return null;
}

Walkthrough

BST: 6 / 2,8 / 0,4,7,9 — find LCA of 2 and 8.

For 2 and 4: start 6 → both < 6 → go left 2 → now 2 is one endpoint and 4 > 2 → from 2 go right to 4’s region… Actually LCA of 2 and 4: walk from 6: both less → 2. At 2: one node is 2 (current), other is 4>2 → still must descend right to 4? Rule: return first node where p and q fall on opposite sides or equal current. At 2, small=2, large=4: current.val(2) >= small and <= large → return 2. Good.

Invariant: BST invariant guarantees first node inside [min(p,q), max(p,q)] is the LCA.

Edge Cases

• One node is ancestor of the other → answer is the ancestor (handled by inclusive range)
• All nodes along one spine — still O(h)

Pitfalls

• Using generic binary-tree LCA on BST and missing O(h) constant-space advantage
• Swapping p/q without normalizing min/max (optional but clearer)

Similar Problems

• 236. Lowest Common Ancestor of a Binary Tree — no BST order; must use different DFS.
• 230. Kth Smallest Element in a BST — same BST walk reasoning.
• 098. Validate Binary Search Tree — reinforces valid ranges on keys.

Variants

• Parent pointers only → different walk up levels.
• Smallest / largest value in common subtree between two nodes.

Mind-Map Tags

#trees #bst #lca #range-split #iterative-walk