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
}

Output: LCA = 2

Example 2

{
  "tree": [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4],
  "a": 6,
  "b": 4
}

Output: LCA = 5

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.