Depth-First Search/Lowest Common Ancestor of a Binary TreeMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Lowest Common Ancestor of a Binary Tree

Depth-First Search·Medium

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

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).

Return the value of the LCA node.

Input convention. The tree is passed as a level-order array with null for missing children. p and q are integer node values guaranteed to exist in the tree.

Examples

Input: values = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

LCA of nodes 5 and 1 is 3.

Input: values = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Node 5 is an ancestor of 4, so LCA is 5.

Input: values = [1,2], p = 1, q = 2

Output: 1

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 tree.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Depth-First Search
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.