Find Lowest Common Ancestor with Parents
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 1650. Lowest Common Ancestor of a Binary Tree III Compute the time and space complexity of your solution
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/
Quick Answer: This question evaluates proficiency with tree data structures and algorithmic problem-solving, specifically reasoning about Lowest Common Ancestor computations on nodes with parent pointers and assessing time and space complexity.
You are given a tree of n nodes labeled 0..n-1 represented by an array parents of length n, where parents[i] is the parent of node i, or -1 if i is the root. Given two node indices p and q, return the index of their lowest common ancestor (the deepest node that is an ancestor of both).
Constraints
- Let n = len(parents).
- Nodes are labeled from 0 to n-1.
- Exactly one index r has parents[r] == -1 (the root).
- parents describes a valid tree (no cycles, every non-root has exactly one parent).
- 0 <= p, q < n.
- 1 <= n <= 200000.
Hints
- Simulate parent pointers using indices and two pointers: when one pointer reaches the root sentinel (-1), redirect it to the other start node.
- Alternatively, collect all ancestors of one node in a set and walk up from the other until you find the first common node.
- Handle the trivial case p == q immediately.