Find lowest common ancestor
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 236. Lowest Common Ancestor of a Binary Tree — Given a binary tree, find the lowest common ancestor (LCA) of two given nodes. Follow-up: how would the solution change if each node had a parent pointer?
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
Quick Answer: This question evaluates understanding of binary tree structure, lowest common ancestor concepts, and competency in algorithmic reasoning and tree traversal within the Coding & Algorithms category.
Given a binary tree represented as a 0-indexed level-order array using null for missing nodes, return the value of the lowest common ancestor (LCA) of two distinct node values p and q. The LCA is the deepest node that has both p and q as descendants (a node can be a descendant of itself). The array follows complete-binary-tree indexing: for any index i, the left child is at 2*i+1 and the right child is at 2*i+2 when within bounds; missing nodes must be represented by null in those positions. Trailing nulls beyond the last non-null index may be omitted. All node values are unique, and both p and q are guaranteed to exist in the tree.
Constraints
- 1 <= n <= 200000 where n is the length of level
- All node values are unique integers
- Both p and q exist in the tree and p != q
- The tree uses complete-binary-tree indexing with null placeholders; trailing nulls past the last non-null index may be omitted
- Values fit in 32-bit signed integers
Solution
from typing import List, Optional, Dict, Set
def lowest_common_ancestor(level: List[Optional[int]], p: int, q: int) -> int:
n = len(level)
if n == 0:
raise ValueError("Tree is empty")
# Validate presence (per constraints, this should hold)
present = {v for v in level if v is not None}
if p == q:
return p
if p not in present or q not in present:
# Should not happen per constraints; return a sentinel if it does
return -1
# Build parent map using complete-binary-tree indexing
parent: Dict[int, int] = {}
for i, val in enumerate(level):
if val is None:
continue
li = 2 * i + 1
ri = 2 * i + 2
if li < n and level[li] is not None:
parent[level[li]] = val
if ri < n and level[ri] is not None:
parent[level[ri]] = val
# Collect ancestors of p (including p)
ancestors: Set[int] = set()
x = p
while True:
ancestors.add(x)
if x in parent:
x = parent[x]
else:
break
# Climb from q until we hit an ancestor of p
y = q
while y not in ancestors:
if y in parent:
y = parent[y]
else:
break
return y
Explanation
We avoid recursion by computing parent pointers directly from the level-order array using complete-binary-tree indexing. After building a map from each node value to its parent's value, we collect all ancestors of p up to the root in a set. Then we climb from q toward the root until we first encounter a value present in that ancestor set; that value is the LCA. This mirrors the classic approach when nodes have parent pointers and works in linear time.
Time complexity: O(n). Space complexity: O(n).
Hints
- Recursive approach: if the current node is p or q, return it; otherwise recurse on left and right. If both sides return non-null, current node is LCA; else propagate the non-null result.
- Iterative approach: compute parent pointers by scanning the array using 2*i+1 and 2*i+2 indices. Then mark all ancestors of p, and climb from q until you hit a marked ancestor.
- If each node had a parent pointer, you could directly mark ancestors of p and ascend from q without building the tree.