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

Lowest Common Ancestor of a Binary Search Tree

Easy TreeBinary TreeDFS LeetCode

Given a binary search tree (BST) and two node values p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that has both p and q as descendants (a node can be a descendant of itself). Use the BST property to solve efficiently without visiting every node.

Example 1:

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
Sample Input
—
Sample Output
—
Constraints
  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique
Test Cases
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).

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