Lowest Common Ancestor of a Binary Search Tree solution and explanation
Google
9 more videos on this problem
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - PythonNeetCode · 6:43 · 363K views
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree (Algorithm Explained)Nick White · 6:36 · 28K views
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Trees (Python)Greg Hogg · 8:48 · 14K views
Lowest Common Ancestor of a Binary Search Tree - LeetCode 235 - PythonDeepti Talesra · 10:54 · 5K views
[Java] Leetcode 235. Lowest Common Ancestor of a Binary Search Tree [Binary Search Tree #4]Eric Programming · 4:34 · 3K views
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree - Interview Prep Ep 137Fisher Coder · 10:24 · 785 views
LCA Of A BST | LeetCode 235 (Easy)Destination FAANG · 10:48 · 771 views
Lowest Common Ancestor of a Binary Search Tree (Java) | Leetcode 235 |Puru Arora · 8:15 · 397 views
Lowest Common Ancestor of a Binary Search Tree - 235. LeetCode - JavaTeddy Smith · 7:58 · 372 views
LeetCode Problem 235: Lowest Common Ancestor of a Binary Search Tree || FAANG Interview || Blind 75KeyStrokes · 11:43 · 320 views
The problem
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.valare unique. p != qpandqwill 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.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
elif p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return rootpublic class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
else if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
else
return root;
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right, p, q);
else if (p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left, p, q);
else
return root;
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var lowestCommonAncestor = function(root, p, q) {
if (!root) return null;
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
else if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
else
return root;
};#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (root == NULL) return NULL;
if (p->val > root->val && q->val > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else if (p->val < root->val && q->val < root->val) {
return lowestCommonAncestor(root->left, p, q);
} else {
return root;
}
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (p.val > root.val && q.val > root.val)
return LowestCommonAncestor(root.right, p, q);
else if (p.val < root.val && q.val < root.val)
return LowestCommonAncestor(root.left, p, q);
else
return root;
}
}This Python function uses recursion to navigate the tree, choosing branches based on node values. The LCA is found by determining when p and q reside on different sides of a node.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to function recursion stack.
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.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
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.right
elif p.val < current.val and q.val < current.val:
current = current.left
else:
return current
return Nonepublic class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode current = root;
while (current != null) {
if (p.val > current.val && q.val > current.val) {
current = current.right;
} else if (p.val < current.val && q.val < current.val) {
current = current.left;
} else {
return current;
}
}
return null;
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* current = root;
while (current != NULL) {
if (p->val > current->val && q->val > current->val) {
current = current->right;
} else if (p->val < current->val && q->val < current->val) {
current = current->left;
} else {
return current;
}
}
return nullptr;
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var lowestCommonAncestor = function(root, p, q) {
let current = root;
while (current) {
if (p.val > current.val && q.val > current.val) {
current = current.right;
} else if (p.val < current.val && q.val < current.val) {
current = current.left;
} else {
return current;
}
}
return null;
};#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode* current = root;
while (current != NULL) {
if (p->val > current->val && q->val > current->val) {
current = current->right;
} else if (p->val < current->val && q->val < current->val) {
current = current->left;
} else {
return current;
}
}
return NULL;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode current = root;
while (current != null) {
if (p.val > current.val && q.val > current.val) {
current = current.right;
} else if (p.val < current.val && q.val < current.val) {
current = current.left;
} else {
return current;
}
}
return null;
}
}This Python code employs a loop to iteratively navigate the BST using comparisons to find the LCA, which ensures efficient space usage.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1) due to iterative nature with no extra space usage.
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).
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode | null,
q: TreeNode | null,
): TreeNode | null {
while (root) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
for {
if root.Val < min(p.Val, q.Val) {
root = root.Right
} else if root.Val > max(p.Val, q.Val) {
root = root.Left
} else {
return root
}
}
}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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode | null,
q: TreeNode | null,
): TreeNode | null {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root.Val < p.Val && root.Val < q.Val {
return lowestCommonAncestor(root.Right, p, q)
}
if root.Val > p.Val && root.Val > q.Val {
return lowestCommonAncestor(root.Left, p, q)
}
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(h), where h is the height of the tree. |
| Iterative Approach | Time Complexity: O(h), where h is the height of the tree. |
| Iteration | – |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive BST Traversal | O(h) | O(h) | When recursion is acceptable and you want concise logic that mirrors BST search |
| Iterative BST Traversal | O(h) | O(1) | Preferred for interviews or memory‑constrained environments since it avoids recursion stack |
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).