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.
Solution
def lowest_common_ancestor(parents: list[int], p: int, q: int) -> int:
"""
Return the index of the lowest common ancestor of nodes p and q
in a rooted tree represented by a parent array.
parents[i] = parent of i, or -1 if i is the root.
"""
# If both nodes are the same, it's their own LCA
if p == q:
return p
a, b = p, q
# In a valid tree, pointers will meet at LCA within at most 2*n steps
while a != b:
a = parents[a] if a != -1 else q
b = parents[b] if b != -1 else p
return a
Explanation
Use two pointers starting at p and q. Each step, move a pointer to its parent; when it reaches the root sentinel (-1), redirect it to the other starting node. This aligns their path lengths so they meet at the lowest common ancestor. If p == q, return p immediately.
Time complexity: O(h) where h is the height of the tree (worst-case O(n)). Space complexity: O(1).
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.