Lowest Common Ancestor of a Binary Search Tree

Medium · Trees

You are given the root of a binary search tree, along with two of its existing nodes p and q. Return the deepest node in the tree that is an ancestor of both p and q, where a node counts as its own ancestor. Use the ordering property of the BST (left subtree values smaller, right subtree values larger) to locate this node efficiently.

Examples

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Why:    2 is in the left subtree and 8 is in the right subtree of 6, so 6 is the split point and the lowest common ancestor.

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Why:    4 lies inside the subtree rooted at 2 (2's own subtree contains 0,4,3), so 2 is itself the ancestor of both.

Input:  root = [2,1], p = 2, q = 1
Output: 2
Why:    1 is a child of 2, and a node counts as its own ancestor, so the ancestor of both is 2.

Constraints

2 <= number of nodes <= 10^5, -10^9 <= node values <= 10^9, all node values are unique, p and q are distinct nodes that exist in the tree

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Lowest Common Ancestor of a Binary Search Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Lowest Common Ancestor of a Binary Search Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.