LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree

LeetCode Problem 235

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to find the Lowest Common Ancestor, commonly abbreviated as LCA, of two nodes in a Binary Search Tree (BST).

A lowest common ancestor of two nodes p and q is the deepest node in the tree that has both p and q as descendants. A node is allowed to be a descendant of itself, which means if one target node lies directly on the path to the other, the ancestor may simply be that node itself.

The input consists of:

• root, the root node of a binary search tree
• p, one target node
• q, another target node

The output should be the tree node representing their lowest common ancestor.

The important detail is that the tree is specifically a Binary Search Tree. In a BST:

• Every node in the left subtree has a smaller value than the current node
• Every node in the right subtree has a larger value than the current node

This property is what allows an efficient solution.

The constraints tell us several important things:

• The tree can contain up to 10^5 nodes, so inefficient algorithms may time out
• All values are unique, which guarantees that every node can be identified by its value
• Both p and q are guaranteed to exist in the tree
• p != q, so we never need to handle identical target nodes

Several edge cases are important:

• One node may be the ancestor of the other
• The root itself may be the LCA
• Both nodes may lie entirely in the left subtree
• Both nodes may lie entirely in the right subtree
• The tree may be highly unbalanced, behaving almost like a linked list

A naive implementation that ignores BST properties may still work, but it would miss an important optimization opportunity.

Approaches

Brute Force Approach

A brute-force solution treats the tree as a normal binary tree and ignores the BST ordering property.

One common strategy is:

1. Build parent pointers for every node using DFS or BFS
2. Store all ancestors of node p
3. Traverse upward from node q
4. The first ancestor also present in p's ancestor set is the LCA

This approach works because every node has exactly one path to the root. Eventually, the upward traversal from q must intersect with the ancestor chain of p.

However, this solution requires extra memory for the parent map and ancestor set. It also performs unnecessary traversal because it ignores the BST structure that already tells us where to search.

Optimal Approach

The key insight comes from the BST ordering property.

Suppose the current node has value x.

• If both p and q are smaller than x, then both nodes must lie in the left subtree
• If both p and q are larger than x, then both nodes must lie in the right subtree
• Otherwise, the current node lies between them, or equals one of them, which means it is the lowest common ancestor

This allows us to walk downward from the root while narrowing the search space at each step.

Because each decision eliminates half of the remaining tree structure, the algorithm is very efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds parent relationships and ancestor sets
Optimal	O(h)	O(1)	Uses BST ordering to directly locate the split point

Here, h represents the height of the tree.

Algorithm Walkthrough

1. Start at the root node of the BST.
2. Compare the values of p and q with the current node's value.
3. If both target values are smaller than the current node's value, move to the left child.

This works because the BST property guarantees both nodes must be in the left subtree. 4. If both target values are larger than the current node's value, move to the right child.

Again, the BST property guarantees both nodes must be in the right subtree. 5. Otherwise, the current node is the split point.

This means:

• one node is on the left and the other is on the right, or
• the current node equals one of the targets

6. Return the current node as the lowest common ancestor.

Why it works

The BST property guarantees that all smaller values lie in the left subtree and all larger values lie in the right subtree. As long as both target nodes lie on the same side of the current node, we can safely continue searching in that subtree. The first node where the targets diverge, or where one target equals the current node, must be the lowest node containing both descendants. Therefore, that node is the LCA.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from typing import Optional

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        p: 'TreeNode',
        q: 'TreeNode'
    ) -> 'TreeNode':

        current = root

        while current:
            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

The implementation begins with a pointer named current initialized to the root node.

Inside the loop, the algorithm compares both target values against the current node's value.

If both targets are smaller, the search moves left. If both are larger, the search moves right. These moves are guaranteed to be correct because of BST ordering.

The else condition handles the critical split point. At this moment, either:

• the targets lie on opposite sides, or
• one target equals the current node

In either case, the current node is the lowest common ancestor, so it is returned immediately.

The iterative approach avoids recursion stack overhead and keeps the space complexity constant.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	current := root

	for current != nil {
		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 nil
}

The Go implementation follows the same logic as the Python solution.

Go uses nil instead of Python's None. Pointer traversal is explicit through *TreeNode references. The algorithm remains iterative, which avoids recursive stack growth even for highly unbalanced trees.

The final return nil is technically unreachable because the problem guarantees both nodes exist in the BST, but it satisfies Go's requirement that all control paths return a value.

Worked Examples

Example 1

Input:

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

Tree structure:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

Step	Current Node	p.val	q.val	Decision
1	6	2	8	One smaller and one larger, return 6

Result:

LCA = 6

The nodes split at the root, so the root is their lowest common ancestor.

Example 2

Input:

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

Step	Current Node	p.val	q.val	Decision
1	6	2	4	Both smaller, move left
2	2	2	4	Current equals p, return 2

Result:

LCA = 2

This demonstrates the important rule that a node can be its own descendant.

Example 3

Input:

root = [2,1]
p = 2
q = 1

Tree:

    2
   /
  1

Step	Current Node	p.val	q.val	Decision
1	2	2	1	Current equals p, return 2

Result:

LCA = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	Visits at most one node per tree level
Space	O(1)	Uses only a few pointer variables

The algorithm traverses downward through the tree without revisiting nodes. In the worst case, it follows a single root-to-leaf path.

For a balanced BST, the height h is O(log n), so the algorithm is very efficient.

For a completely unbalanced BST, the height becomes O(n), making the worst-case runtime linear.

The iterative implementation uses constant extra memory because it does not allocate auxiliary data structures or recursion stacks.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        current = root

        while current:
            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

# Build example BST
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

sol = Solution()

# Example 1
assert sol.lowestCommonAncestor(root, root.left, root.right).val == 6  # nodes split at root

# Example 2
assert sol.lowestCommonAncestor(root, root.left, root.left.right).val == 2  # one node is ancestor

# Example 3
small_root = TreeNode(2)
small_root.left = TreeNode(1)

assert sol.lowestCommonAncestor(
    small_root,
    small_root,
    small_root.left
).val == 2  # minimal tree

# Both nodes in left subtree
assert sol.lowestCommonAncestor(
    root,
    root.left.left,
    root.left.right.right
).val == 2  # LCA inside left subtree

# Both nodes in right subtree
assert sol.lowestCommonAncestor(
    root,
    root.right.left,
    root.right.right
).val == 8  # LCA inside right subtree

# Deep descendant relationship
assert sol.lowestCommonAncestor(
    root,
    root.left,
    root.left.right.left
).val == 2  # ancestor-descendant case

# Highly skewed tree
skewed = TreeNode(1)
skewed.right = TreeNode(2)
skewed.right.right = TreeNode(3)
skewed.right.right.right = TreeNode(4)

assert sol.lowestCommonAncestor(
    skewed,
    skewed.right,
    skewed.right.right.right
).val == 2  # skewed BST

Test	Why
Nodes split at root	Validates root as LCA
One node is ancestor	Confirms descendant rule
Minimal tree	Tests smallest valid input
Both nodes in left subtree	Ensures left traversal works
Both nodes in right subtree	Ensures right traversal works
Deep ancestor relationship	Confirms ancestor handling
Highly skewed tree	Tests worst-case BST height

Edge Cases

One Node Is the Ancestor of the Other

A very common source of bugs occurs when one target node directly contains the other in its subtree. Some incorrect implementations continue searching deeper and miss the correct answer.

For example:

    2
   /
  1

If p = 2 and q = 1, the correct answer is 2.

The implementation handles this naturally because the algorithm returns immediately when the current node lies between the two targets or equals one of them.

The Root Is the Lowest Common Ancestor

Another important case occurs when the targets lie in different subtrees of the root.

For example:

      6
     / \
    2   8

One target is smaller than 6 and the other is larger than 6.

The algorithm immediately detects the split and returns the root without unnecessary traversal.

Highly Unbalanced Trees

A BST can degenerate into a linked list:

1
 \
  2
   \
    3
     \
      4

Recursive implementations may risk stack overflow for extremely deep trees.

The iterative implementation avoids this issue entirely because it uses a loop instead of recursion. Even when the height becomes O(n), the memory usage remains constant.