Find the Lowest Common Ancestor in a Binary Tree
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Find the Lowest Common Ancestor in a Binary Tree
### Problem
Implement `lowestCommonAncestor(left, right, root, first, second) -> nodeId`.
The binary tree has node IDs `0` through `n - 1`. Arrays `left` and `right` describe its children: a value of `-1` means that child is absent. Return the ID of the lowest node whose subtree contains both `first` and `second`. A node is a descendant of itself, so if `first == second`, return that node.
### Portable Contract
- `left` and `right` are integer arrays of the same length `n`, with `1 <= n <= 12,000`.
- `0 <= root, first, second < n`.
- Every nonnegative child value is less than `n`.
- The arrays describe one valid binary tree: every node is reachable from `root` exactly once, and there are no cycles or shared children.
- Do not modify either input array.
- Let `B` be the compact UTF-8 JSON byte length of `[left,right,root,first,second]`, with no whitespace outside strings and every comma, bracket, minus sign, and digit counted. Inputs satisfy `B <= 160,000`. The integer result adds at most six serialized bytes.
- Target `O(n)` time and `O(n)` auxiliary space. The implementation must handle a tree of height `n` without depending on a shallow recursion limit.
The arguments and result project directly to all four languages: integer arrays plus integer scalars in Python and JavaScript, `List<Integer>` plus `int` in Java, and `vector<int>` plus `int` in C++.
```hint Identify what must be known about both targets
A node becomes the answer at the first place where information from the two target searches meets, including the case where that node is itself a target.
```
```hint Account for a degenerate tree
Choose traversal state that remains safe when every node has only one child.
```
### Examples
```text
left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
root = 0
first = 3
second = 4
nodeId = 1
```
```text
left = [1, 2, 3, -1]
right = [-1, -1, -1, -1]
root = 0
first = 1
second = 3
nodeId = 1
```
### Discussion Requirements
- State the invariant used to propagate target information toward the root.
- Explain why one target being an ancestor of the other is not a special failure case.
- Compare a one-pass subtree method with building parent pointers and ancestor sets.
- Include tests for equal targets, root as the answer, nodes in different subtrees, and a maximum-height tree.
Quick Answer: Find the lowest common ancestor of two nodes in a binary tree represented by child-index arrays. The exercise evaluates tree invariants, ancestor edge cases, iterative traversal choices, and safety on a maximum-height tree.
Implement `lowestCommonAncestor(left, right, root, first, second)`.
A binary tree has `n` nodes whose IDs are `0` through `n - 1`. Two integer
arrays of length `n` describe its children: `left[i]` is the ID of node `i`'s
left child and `right[i]` is the ID of node `i`'s right child, where the
sentinel `-1` means that child is absent. The tree is rooted at node `root`.
Return the ID of the **lowest** node whose subtree contains both `first` and
`second`. A node counts as a descendant of itself, so if `first == second` the
answer is that node, and if one target is an ancestor of the other the answer
is the ancestor.
**Output is a single integer and it is unique.** In a rooted tree the common
ancestors of two nodes form one root-to-node path, so exactly one of them is
lowest. There is no ordering, tie-break, or formatting choice to make: return
that node ID.
### Input shape
The five arguments arrive positionally in every language. `left` and `right`
are integer arrays (`java.util.List<Integer>` in Java, `const
std::vector<int>&` in C++); `root`, `first`, and `second` are plain integers.
Neither array may be modified.
### Example 1
```text
left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
root = 0
first = 3
second = 4
-> 1
```
Node 0 has children 1 and 2; node 1 has children 3 and 4. Node 1 is the lowest
node whose subtree holds both 3 and 4.
### Example 2
```text
left = [1, 2, 3, -1]
right = [-1, -1, -1, -1]
root = 0
first = 1
second = 3
-> 1
```
The tree is the chain `0 -> 1 -> 2 -> 3`. Node 1 is an ancestor of node 3, and
a node is a descendant of itself, so the answer is 1 rather than 0.
Constraints
- `left` and `right` are integer arrays of the same length `n`, with `1 <= n <= 12,000`
- `0 <= root, first, second < n`
- Each entry of `left` and `right` is either `-1` (that child is absent) or a node ID `v` with `0 <= v < n`; every nonnegative child value is less than `n`
- The arrays describe one valid binary tree rooted at `root`: every node `0..n-1` is reachable from `root` exactly once, and there are no cycles and no shared children. Consequently `first` and `second` always exist and the lowest common ancestor is always defined
- `first == second` is legal, and one target may be an ancestor of the other; neither is an error case
- Every input value lies in `[-1, 11,999]` and the returned node ID lies in `[0, 11,999]`, so every quantity is well inside the signed 32-bit range: `int` is the correct type in Java and C++, and no 64-bit widening is needed anywhere
- `left` and `right` must not be modified
- Let `B` be the compact UTF-8 JSON byte length of `[left, right, root, first, second]`, with no whitespace outside strings and every comma, bracket, minus sign, and digit counted. Inputs satisfy `B <= 160,000`. The integer result adds at most six serialized bytes
- The tree height can be as large as `n`: a degenerate chain of 12,000 nodes is a legal input, so the solution must not depend on a shallow recursion limit
- Target `O(n)` time and `O(n)` auxiliary space
Examples
Input: ([-1], [-1], 0, 0, 0)
Expected Output: 0
Explanation: n = 1. The only node is 0, and a node is a descendant of itself, so the lowest common ancestor of 0 and 0 is 0.
Input: ([1,3,-1,-1,-1], [2,4,-1,-1,-1], 0, 3, 4)
Expected Output: 1
Explanation: Node 1 has children 3 and 4, so 1 is the lowest node whose subtree contains both.
Hints
- A node can only be the answer if something is known about BOTH targets there. Decide what one piece of per-node information about a single target would be, and where the two pieces first meet.
- One target being an ancestor of the other is not a special case if you take seriously that a node is a descendant of itself. Check that your rule already returns the right node there before adding a branch for it.
- A legal input can be a chain of 12,000 nodes, so whatever traversal you choose has to survive 12,000 levels without relying on the language's default call-stack depth. An explicit stack or queue, or a parent array, all sidestep that.