Lowest Common Ancestor in a Binary Tree

Try to solve the Lowest Common Ancestor in a Binary Tree problem.

Statement

Given the root node of a binary tree with nn 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:

  • 2n5002 \leq n \leq 500
  • All Node.data are unique.
  • p !=!= q
  • p and q exist in the tree.

Examples

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy