Skip to main content

235. Lowest Common Ancestor of a Binary Search Tree

medium

Find the lowest common ancestor of two nodes in a BST. The sorted-tree property lets you decide direction at every step — no need to traverse the whole tree.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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).'

Constraints

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

Examples

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 per the LCA definition.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If both p and q are less than the current node, the LCA must be in the left subtree.

Hint 2

If both are greater, it must be in the right subtree.

Hint 3

Otherwise (split or one of them equals the node), the current node IS the LCA.

Solution approach

Reveal approach

Walk down the BST using the sorted property. At each node: if both p.val and q.val are less than node.val, descend left; if both are greater, descend right; otherwise (the values split or one matches the current node), return node — this is the LCA. Iterative version uses constant extra space; recursive version uses O(h) stack. Either way, O(h) time where h is tree height, O(log n) on average for a balanced BST.

Complexity

Time
O(h)
Space
O(1) iterative

Related patterns

  • bst
  • dfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Lowest Common Ancestor of a Binary Search Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →