Medium

Quiz

#236 Lowest Common Ancestor of a Binary Tree

APPROACH

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

The LCA is defined as the deepest node that has both p and q as descendants, where a node may be a descendant of itself.

Example 1:

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

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

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

Output: 5

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

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

Output: 1

1 of 4

1:00

What is the optimal approach for this problem?