mafeshsho8lmafeshsho8l
Get Started
All coding questions

Lowest Common Ancestor of a BST

medium
NeetCode 150treesbst

Problem

Given the root of a binary search tree and two of its nodes, return their lowest common ancestor, the deepest node that has both given nodes as descendants. A node may be a descendant of itself.

Examples

Input: BST rooted at 6 with nodes 2 and 8
Output: 6
The two nodes split at the root.
Input: BST rooted at 6 with nodes 2 and 4
Output: 2
Both lie in the left subtree under 2.

Constraints

  • • 2 <= number of nodes <= 10^5
  • • All node values are unique
  • • Both targets exist in the tree
Hints(tap to reveal)
  • 1. BST ordering tells you which way to descend.
  • 2. The split point is the answer.
Optimal approach(spoiler)
  1. Start at the root and compare both target values to the current node.
  2. If both are smaller, go left; if both are larger, go right.
  3. Otherwise the current node is where the paths diverge, the ancestor.
  4. No recursion stack is needed for the iterative form.
  5. O(h) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor