Introduction

LeetCode 235 – Lowest Common Ancestor of a Binary Search Tree is one of the most important BST interview problems.

This problem helps you understand:

1. Binary Search Tree properties
2. Recursive traversal
3. Tree navigation
4. Ancestor relationships
5. Optimized searching

It is frequently asked in coding interviews because it combines tree traversal with BST optimization.

Problem Link

🔗 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Problem Statement

Given:

1. Root of a Binary Search Tree
2. Two nodes p and q

Return:

The LCA is the lowest node in the tree that has both nodes as descendants.

A node can also be a descendant of itself.

Example 1

Input

Output

Example 2

Input

Output

Understanding the BST Property

A Binary Search Tree follows:

Example:

This property allows us to find the LCA efficiently.

Key Observation

There are only three possible cases:

Case 1

Both nodes are smaller than root.

Case 2

Both nodes are greater than root.

Case 3

One node is on the left and the other is on the right.

OR

One node equals root.

Then:

Intuition

Suppose:

Now:

This means:

1. One node is in left subtree
2. One node is in right subtree

So:

Hence:

Brute Force Approach

Idea

1. Find path from root to p
2. Find path from root to q
3. Compare both paths
4. Last common node is the LCA

Brute Force Complexity

Time Complexity

Space Complexity

Extra path storage required.

Optimized BST Approach

Using BST properties:

1. No need to store paths
2. No need to traverse entire tree
3. Move intelligently

This gives a much cleaner solution.

Java Solution

Cleaner Recursive Version

Iterative Approach

We can also solve this without recursion.

Iterative Java Solution

Dry Run

Input

Step 1

Current root:

Check:

One node is on left.

One node is on right.

So:

Final Output

Another Dry Run

Input

Step 1

Current root:

Both nodes smaller than 6.

Move left.

Step 2

Current root:

Now:

So:

Why This Works

BST ordering helps us eliminate half the tree at every step.

If:

then LCA must exist in left subtree.

If:

then LCA must exist in right subtree.

Otherwise:

which becomes the Lowest Common Ancestor.

Time Complexity Analysis

Optimized BST Solution

Average Time Complexity

Because BST halves search space.

Worst Case Time Complexity

Occurs when BST becomes skewed.

Space Complexity

Recursive

Where:

Iterative

No recursion stack used.

Interview Explanation

In interviews, explain:

Since this is a BST, we can use node ordering to decide whether both nodes lie in the left subtree, right subtree, or on different sides. The first split point becomes the Lowest Common Ancestor.

This demonstrates:

1. BST understanding
2. Tree recursion
3. Search optimization
4. Efficient traversal logic

Common Mistakes

1. Treating It Like a Normal Binary Tree

This problem becomes easier because it is a BST.

Use BST properties.

2. Forgetting Split Point Logic

The LCA occurs when:

or vice versa.

3. Traversing Entire Tree

Unnecessary.

BST lets us eliminate half the tree.

4. Confusing Ancestor Definition

A node can be ancestor of itself.

Important for cases like:

Answer becomes:

FAQs

Q1. Why is BST important here?

BST ordering allows efficient searching.

Without BST property, we need a completely different approach.

Q2. Can this be solved iteratively?

Yes.

Iterative traversal is even more space-efficient.

Q3. Is recursion necessary?

No.

Both recursive and iterative solutions work.

Q4. What is the Lowest Common Ancestor?

The deepest node that has both target nodes as descendants.

Conclusion

LeetCode 235 is an excellent BST problem for mastering:

1. BST properties
2. Recursive traversal
3. Tree navigation
4. Optimized searching
5. Ancestor-based reasoning

The main insight is:

In a BST, the first node where paths to p and q split becomes the Lowest Common Ancestor.

Once this concept becomes intuitive, many BST interview problems become much easier to solve.