Watch 10 video solutions for Lowest Common Ancestor of a Binary Search Tree, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by take U forward has 379,697 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 deepest node in the tree that has both nodes as descendants. Because the tree follows BST ordering rules, you can locate the ancestor without exploring every branch.
Approach 1: Recursive BST Traversal (Time: O(h), Space: O(h))
This approach relies on the defining property of a Binary Search Tree: values in the left subtree are smaller than the root, and values in the right subtree are larger. Compare the values of p and q with the current node. If both are smaller, the LCA must be in the left subtree, so recurse left. If both are larger, recurse right. When the current node lies between the two values (or matches one of them), that node is the lowest common ancestor. The recursion follows a single path from root to the split point, giving O(h) time where h is tree height and O(h) stack space. This solution naturally fits problems involving tree traversal and depth-first search.
Approach 2: Iterative BST Traversal (Time: O(h), Space: O(1))
The iterative version applies the exact same BST insight but removes recursion. Start at the root and repeatedly compare p and q with the current node. If both values are smaller, move to node.left. If both are larger, move to node.right. Otherwise, the current node is the split point where one node falls on each side (or one equals the current node), so it must be the LCA. Because you only follow one path down the tree and maintain a single pointer, the algorithm runs in O(h) time with O(1) additional space.
The key insight is recognizing that a BST removes the need to search both subtrees. In a general binary tree you would need a full DFS to check where each node exists, but BST ordering tells you exactly which direction to move.
Recommended for interviews: The iterative BST traversal is typically preferred. It demonstrates that you understand how BST ordering eliminates unnecessary exploration and reduces memory overhead. The recursive version is still acceptable and often quicker to write, but the iterative approach highlights deeper control over tree traversal and space optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive BST Traversal | O(h) | O(h) | Clean and intuitive solution when recursion is acceptable |
| Iterative BST Traversal | O(h) | O(1) | Preferred in interviews when you want constant auxiliary space |