Solution: Lowest Common Ancestor of a Binary Tree

Understand how to find the lowest common ancestor of two nodes in a binary tree by applying a depth-first search approach. This lesson guides you through the recursive strategy, the use of tracking variables, and the logic behind identifying the ancestor efficiently. You will learn how to analyze and optimize this common tree problem with clear practical insight.

We'll cover the following...

Statement
Solution

Statement

Given the root node of a binary tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, p and q.

Note: The lowest common ancestor of two nodes, p and q, is defined as the lowest node in the binary tree that has both p and q as descendants.

A node can also be a descendant of itself. For example, if q is a descendant of p, and we know that p is a descendant of itself, then p will be the lowest common ancestor of p and q.

Constraints:

$2 \leq n \leq 500$

...