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:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q will exist in the BST.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.
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.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to the recursion stack.
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.
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.
| 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. |
| 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 |
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python • NeetCode • 346,743 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode