Lowest Common Ancestor of a Binary Search Tree

The key idea

In a BST the values are ordered, so the lowest common ancestor is the first node where p and q fall on opposite sides (or one equals the node). Walk down comparing both values to the current node and you never need to look at both subtrees.

Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes p and q in the tree.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants, where we allow a node to be a descendant of itself. So if p is an ancestor of q, the LCA is p itself.

The tree is a valid BST: for any node, every value in its left subtree is smaller and every value in its right subtree is larger. You are guaranteed that both p and q exist in the tree and that p is not equal to q.

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

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

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

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

Complexity

Time: O(h) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →