Skip to content
Onsite
15 / 29

Lowest Common Ancestor of a Binary Tree

MediumP1Coding

Given a binary tree and two nodes p and q that both exist in it, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as a descendant of itself.

All node values are unique. p and q are given as values; the harness resolves them to the nodes inside the tree, and the node you return is compared by its value.

Tree nodes have val, left and right. The class TreeNode is already defined for you. The tree arrives in level-order form (as in the examples) and you receive its root, which is null for an empty tree.

Example 1

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

Example 2

Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
Why
5 is an ancestor of 4 and of itself.

Example 3

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

Constraints

  • The number of nodes is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q and both exist in the tree.

Hints

Run checks the 3 visible tests, Submit all 9.