Medium · Trees

N-ary Tree 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

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Trees problems