Medium · Trees

Find lowest common ancestor

Given the root of an N-ary tree and two nodes a and b that are both in it, return their lowest common ancestor: the deepest node that has both a and b as descendants, where a node counts as a descendant of itself.

Examples

Example 1

tree=[3,5,1,6,2,0,8,null,null,7,4], a=7, b=4 (binary-indexed slots: child indices 2i+1 and 2i+2)

Output: LCA = 2

Example 2

tree=[3,5,1,6,2,0,8,null,null,7,4], a=6, b=4 (binary-indexed slots: child indices 2i+1 and 2i+2)

Output: LCA = 5

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.

More Trees problems