All problems
MediumTrees

Lowest Common Ancestor of a Binary Search Tree

amazonmetamicrosoftlinkedinapple

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

Examples

Example 1
        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5
Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output
6

The LCA of nodes 2 and 8 is 6. Node 2 is in the left subtree and node 8 is in the right subtree, so the root (6) is their lowest common ancestor.

Example 2
        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5
Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output
2

The LCA of nodes 2 and 4 is 2. Node 4 is a descendant of node 2, and 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

The root node 2 is the ancestor of node 1, and since a node is its own descendant, the LCA is 2.

Constraints

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

Optimal complexity

Time

O(h)

Space

O(1)

One problem, two ways to prep

Choose between solo practice and interview simulation

Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.

Try 5-Minute Audio InterviewAI Interview Mode