medium

Lowest Common Ancestor of a Binary Tree

Given the root of 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 as descendants (a node counts as its own descendant).

Constraints

2 ≤ number of nodes ≤ 10^5
All node values unique
p and q exist in the tree

Examples

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

out: 3

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

out: 5

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.