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
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.