Medium · Trees

Lowest Common Ancestor of a Binary Tree

Given a binary tree as a level-order array tree (null marks a missing node) and two indices p and q of distinct nodes in that array, return the lowest common ancestor of those two nodes: the deepest node whose subtree contains both (a node is in its own subtree).

Examples

Example 1

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

Output: LCA = 3

Example 2

{
  "tree": [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4],
  "p": 1,
  "q": 10
}

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.