Lowest Common Ancestor in an Explicit Binary Tree
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
Find the lowest common ancestor of two nodes in a rooted binary tree. A node counts as its own ancestor. The answer is the deepest node that is an ancestor of both targets.
The report identifies the LCA problem by name without a variant or representation. This executable practice version explicitly chooses an arbitrary binary tree with existing target nodes and the array representation below.
Implement `lowest_common_ancestor(left, right, root, p, q) -> int`:
- `left: int[]` and `right: int[]` have the same length `n`.
- Node IDs are the integers from `0` through `n - 1`. `left[i]` and `right[i]` identify node `i`'s children; `-1` means no child.
- `root: int` is the root node ID, and `p: int`, `q: int` are target node IDs.
- Return the node ID of their lowest common ancestor.
### Constraints & Assumptions
- `1 <= n <= 100000`.
- The arrays describe a valid rooted binary tree: all nodes are reachable from `root`, there are no cycles, and every non-root node has exactly one parent.
- Both targets exist and may be identical. IDs identify nodes; their numeric order has no relationship to tree position.
- The tree is not required to satisfy any binary-search-tree ordering.
- A target can be an ancestor of the other target. The tree may be a chain, so do not assume shallow recursion.
### Examples
```text
left = [1, -1, -1]
right = [2, -1, -1]
root = 0, p = 1, q = 2
result = 0
```
```text
left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
root = 0, p = 3, q = 4
result = 1
```
```hint Locate where ancestry paths meet
The numeric IDs do not provide a search direction. Use the actual parent-child relationships, either by tracing ancestry or by combining information from subtrees.
```
Overview: Find the lowest common ancestor in a binary tree using explicit child arrays, including identical targets, ancestor targets, and deep trees.
Find the lowest common ancestor of two nodes in a rooted binary tree. A node counts as its own ancestor. The answer is the deepest node that is an ancestor of both targets.
The report identifies the LCA problem by name without a variant or representation. This executable practice version explicitly chooses an arbitrary binary tree with existing target nodes and the array representation below.
Implement `lowest_common_ancestor(left, right, root, p, q) -> int`:
- `left: int[]` and `right: int[]` have the same length `n`.
- Node IDs are the integers from `0` through `n - 1`. `left[i]` and `right[i]` identify node `i`'s children; `-1` means no child.
- `root: int` is the root node ID, and `p: int`, `q: int` are target node IDs.
- Return the node ID of their lowest common ancestor.
### Constraints & Assumptions
- `1 <= n <= 100000`.
- The arrays describe a valid rooted binary tree: all nodes are reachable from `root`, there are no cycles, and every non-root node has exactly one parent.
- Both targets exist and may be identical. IDs identify nodes; their numeric order has no relationship to tree position.
- The tree is not required to satisfy any binary-search-tree ordering.
- A target can be an ancestor of the other target. The tree may be a chain, so do not assume shallow recursion.
### Examples
```text
left = [1, -1, -1]
right = [2, -1, -1]
root = 0, p = 1, q = 2
result = 0
```
```text
left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
root = 0, p = 3, q = 4
result = 1
```
```hint Locate where ancestry paths meet
The numeric IDs do not provide a search direction. Use the actual parent-child relationships, either by tracing ancestry or by combining information from subtrees.
```
Constraints
- 1 <= n <= 100000; left and right have length n and use child IDs 0 through n-1 or -1.
- All nodes form one valid rooted binary tree reachable from root; no cycles and one parent per nonroot node.
- Both targets exist and may be identical or ancestral to one another.
- Node IDs have no tree-order meaning and the tree need not be a BST.
- Return the deepest common ancestor ID; a node is its own ancestor and deep chains are valid.
Examples
Input: ([1, -1, -1], [2, -1, -1], 0, 1, 2)
Expected Output: 0
Explanation: Different root subtrees meet at the root.
Input: ([1, 3, -1, -1, -1], [2, 4, -1, -1, -1], 0, 3, 4)
Expected Output: 1
Explanation: Siblings can meet below the root.