Lowest Common Ancestor of a Binary Search Tree Easy 0 attempts
LeetCode ↗

Lowest Common Ancestor of a Binary Search Tree

Easy TreeBinary TreeDFS LeetCode

You're given the root of a binary search tree (BST) along with two node values p and q known to exist in it. Return the value of their lowest common ancestor (LCA) — the deepest node in the tree that has both p and q somewhere below it (a node counts as its own descendant too). Since the tree is a BST, you can lean on its ordering property to locate the LCA without touching every node.

Input Format
Implement lowestCommonAncestorOfABinarySearchTree(root, p, q). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = [6,2,8,0,4,7,9,null,null,3,5]
p = 2
q = 4
Output
2
Constraints
  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique
Test Cases (2)
Case 1
Args: [[6,2,8,0,4,7,9,null,null,3,5],2,8] Expected: 6
Case 2
Args: [[6,2,8,0,4,7,9,null,null,3,5],2,4] Expected: 2
Topics
TreeBinary TreeDFS

Approach: BST Property

If both p and q are smaller than root, LCA is in the left subtree. If both are larger, LCA is in the right subtree. Otherwise, the current root is the LCA (the split point).

javascript
function lowestCommonAncestorOfABinarySearchTree(root, p, q) {
  while (root) {
    if (p < root.val && q < root.val) root = root.left;
    else if (p > root.val && q > root.val) root = root.right;
    else return root.val;
  }
  return -1;
}

Time Complexity: O(H) where H is tree height

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript