Skip to main content
Talentd

Lowest Common Ancestor of a Binary Search Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Search TreeBinary Tree23 min readAsked at: Amazon, Microsoft, Apple +7
Practice this problem

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Approach Overview

Problem Overview: Given a Binary Search Tree (BST) and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node in the tree that has both nodes as descendants. Because the structure is a BST, every node follows the rule left < root < right, which allows you to locate the ancestor without scanning the entire tree.

Approach 1: Recursive BST Traversal (O(h) time, O(h) space)

The BST property gives a direct way to locate the ancestor. Start from the root and compare the values of p and q with the current node. If both values are smaller than the current node, the LCA must be in the left subtree. If both are larger, move to the right subtree. The first node where the values split (one on each side) is the lowest common ancestor. The recursion follows a single path from the root down the tree, so the time complexity is O(h), where h is the tree height, and recursion adds O(h) call stack space.

This approach naturally mirrors how you search in a Binary Search Tree. It is concise and easy to reason about during interviews because each recursive step eliminates half of the search space.

Approach 2: Iterative Traversal (O(h) time, O(1) space)

The iterative version applies the exact same BST insight but replaces recursion with a loop. Start from the root and repeatedly compare p.val and q.val with the current node value. If both are smaller, move to node.left. If both are larger, move to node.right. When the current node lies between the two values (or equals one of them), you have found the LCA.

This method walks down only one branch of the tree, so the time complexity remains O(h). Because it uses a simple pointer traversal instead of recursive calls, the space complexity improves to O(1). In balanced BSTs the height is O(log n), but in the worst case of a skewed tree it becomes O(n).

The approach relies heavily on the ordering guarantee of a tree that satisfies BST rules. Unlike general Depth-First Search LCA problems, you never need to explore both subtrees.

Recommended for interviews: The iterative BST traversal is usually the expected optimal solution because it runs in O(h) time with constant space. The recursive version still demonstrates a solid understanding of BST structure and is often written faster during interviews. Strong candidates quickly recognize that the BST ordering eliminates the need for full DFS or path tracking.

Approach 1: Recursive Approach

This method exploits the properties of a BST. The idea is to traverse the tree starting from the root. If both p and q are greater than the current node, then the LCA lies in the right subtree. If both are smaller, then it lies in the left subtree. Otherwise, the current node is the LCA.

This C code implements the recursive approach by checking if both nodes' values are either greater or less than the current node. If so, recursively proceed to the right or left subtree, respectively. Otherwise, return the current node as the LCA.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Approach

Instead of recursion, this method uses a while loop to traverse the tree. Starting from the root, check if both nodes are greater or smaller than the current node to decide whether to proceed to the right or left subtree respectively. If neither, we've found the LCA.

This C implementation uses an iterative approach via a loop to find the LCA. It makes use of BST properties to decide movement between left and right nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1) since it does not use extra space beyond variables.

Try this approach in the editor →

Approach 3: Iteration

Starting from the root node, we traverse the tree. If the current node's value is less than both p and q values, it means that p and q should be in the right subtree of the current node, so we move to the right child. If the current node's value is greater than both p and q values, it means that p and q should be in the left subtree, so we move to the left child. Otherwise, it means the current node is the lowest common ancestor of p and q, so we return the current node.

The time complexity is O(n), where n is the number of nodes in the binary search tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Approach 4: Recursion

We can also use a recursive approach to solve this problem.

We first check if the current node's value is less than both p and q values. If it is, we recursively traverse the right subtree. If the current node's value is greater than both p and q values, we recursively traverse the left subtree. Otherwise, it means the current node is the lowest common ancestor of p and q, so we return the current node.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary search tree.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to the recursion stack.

Iterative Approach

Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1) since it does not use extra space beyond variables.

Iteration—
Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive BST TraversalO(h)O(h)When recursion is acceptable and you want concise logic that mirrors BST search
Iterative BST TraversalO(h)O(1)Preferred for interviews or memory‑constrained environments since it avoids recursion stack

Video Solution

Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python • NeetCode • 363,368 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lowest Common Ancestor of a Binary Search Tree easy or hard?
The problem is generally rated Medium because it requires recognizing and exploiting the Binary Search Tree property. Once that insight is clear, the implementation is straightforward and often fits in a few lines of code.
Lowest Common Ancestor of a Binary Search Tree Python/Java solution
Python and Java solutions typically implement either recursion or an iterative loop starting from the root. Both compare node values with p and q to decide whether to move left or right. The logic is identical across languages and runs in O(h) time.
How to solve Lowest Common Ancestor of a Binary Search Tree in O(n)?
A general tree approach performs a DFS traversal and returns the node where the paths to p and q diverge. That solution explores both subtrees and runs in O(n) time with O(h) recursion space. For BSTs specifically, the ordering property allows a faster O(h) solution by following a single branch from the root.
What is the best approach for Lowest Common Ancestor of a Binary Search Tree?
The optimal approach uses the Binary Search Tree ordering property while traversing from the root. If both nodes are smaller than the current node, move left; if both are larger, move right. The first node where the values diverge is the lowest common ancestor. This runs in O(h) time where h is the tree height and requires O(1) space in the iterative version.
Is Lowest Common Ancestor of a Binary Search Tree asked at Google/Amazon/Meta?
Lowest Common Ancestor problems are common interview questions at companies like Google, Amazon, Meta, and Microsoft. Variants appear with Binary Trees, Binary Search Trees, or parent pointers. The BST version is frequently used to test understanding of tree traversal and ordering properties.
What data structure is used in Lowest Common Ancestor of a Binary Search Tree?
The problem uses a Binary Search Tree data structure. The solution relies on the BST ordering rule where all nodes in the left subtree are smaller than the root and all nodes in the right subtree are larger, enabling efficient ancestor discovery.
What is the time complexity of Lowest Common Ancestor of a Binary Search Tree?
The standard BST-based solution runs in O(h) time, where h is the height of the tree. In a balanced BST this becomes O(log n). In the worst case of a skewed tree, the height becomes n and the complexity degrades to O(n).

Ready to solve this problem?

Practice Lowest Common Ancestor of a Binary Search Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Tree

Next

Lowest Common Ancestor of a Binary Tree II