Medium

Lowest Common Ancestor of a Binary Tree III

LAB

Given parent pointers as [node,parent] rows and two node values, return their lowest common ancestor value.

EXAMPLES

Example 1

Input
{
  "parents": [
    [
      3,
      -1
    ],
    [
      5,
      3
    ],
    [
      1,
      3
    ],
    [
      6,
      5
    ],
    [
      2,
      5
    ],
    [
      0,
      1
    ],
    [
      8,
      1
    ]
  ],
  "p": 6,
  "q": 2
}

Output
5

FUNCTION SHAPE

parents: intMatrixp: intq: int→int

SOLUTION NOTE

Classic trick: p travels x to LCA then z to root. q travels y to LCA then z to root. If p starts at og_p and q starts at og_q, both travel x+y+z steps to meet at LCA!

Reveal reference solution +

pythonREFERENCE

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
    og_p, og_q = p, q
    while p != q:
        p = p.parent if p else og_q
        q = q.parent if q else og_p
    return p

TimeO(h)

SpaceO(1)

Open on LeetCode ↗