Lowest Common Ancestor of a Binary Search Tree

Asked byLinkedInFacebookAmazonAppleGoogleMicrosoft

Problem

Given a binary search tree and two of its nodes p and q, find the lowest node in the tree that has both p and q as descendants (a node is considered a descendant of itself).

Examples

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

Constraints

All node values are unique, and p and q both exist in the tree.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

Original problem on LeetCode ↗