List the Nodes on the Path Between Two Nodes of a Binary Tree
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a binary tree and two of its nodes, return the nodes on the path that connects them.
### Function Signature
```python
def path_between_nodes(left: list[int], right: list[int], u: int, v: int) -> list[int]:
```
### Rules
- The tree has `n` nodes numbered `0` to `n - 1`, and node `0` is the root. `left[i]` and `right[i]` are the indices of node `i`'s left and right children, or `-1` when that child is missing.
- In a tree, exactly one path connects two nodes: the sequence of nodes from `u` to `v` in which every two consecutive nodes are a parent and its child, and no node appears twice.
- Return the indices of the nodes on that path in order, starting with `u` and ending with `v`. If `u == v`, return `[u]`.
### Constraints
- `1 <= n == len(left) == len(right) <= 10^5`
- Every child index is `-1` or between `1` and `n - 1`, every node other than `0` is the child of exactly one node, and the links form a single binary tree rooted at node `0`.
- `0 <= u <= n - 1` and `0 <= v <= n - 1`
- The tree can be a single path, so its depth can reach `n`.
### Examples
All three examples use this tree, drawn with node indices:
```text
left = [1, 3, -1, -1, 6, -1, -1]
right = [2, 4, 5, -1, -1, -1, -1]
0
/ \
1 2
/ \ \
3 4 5
/
6
```
**Example 1**
```text
Input: left = [1, 3, -1, -1, 6, -1, -1], right = [2, 4, 5, -1, -1, -1, -1], u = 6, v = 5
Output: [6, 4, 1, 0, 2, 5]
```
The path climbs from node 6 to the root and then descends to node 5.
**Example 2**
```text
Input: left = [1, 3, -1, -1, 6, -1, -1], right = [2, 4, 5, -1, -1, -1, -1], u = 3, v = 6
Output: [3, 1, 4, 6]
```
The path turns at node 1 and never reaches the root.
**Example 3**
```text
Input: left = [1, 3, -1, -1, 6, -1, -1], right = [2, 4, 5, -1, -1, -1, -1], u = 0, v = 6
Output: [0, 1, 4, 6]
```
Node 0 is an ancestor of node 6, so the path only descends.
Overview: Given a binary tree stored as child-index arrays and two node indices, return the nodes on the unique path between them, from the first node to the second. It tests parent tracking, ancestor reasoning and handling cases where one node lies above the other.
You are given a binary tree with `n` nodes numbered `0` to `n - 1`, and node `0` is the root. `left[i]` and `right[i]` are the indices of node `i`'s left and right children, or `-1` when that child is missing.
In a tree, exactly one path connects two nodes: the sequence of nodes from `u` to `v` in which every two consecutive nodes are a parent and its child, and no node appears twice.
Implement `path_between_nodes(left, right, u, v)`, which returns the indices of the nodes on that path in order, starting with `u` and ending with `v`. If `u == v`, return `[u]`.
Apart from the root being node `0`, the constraints do not tie a node's index to its position in the tree (a child may have a smaller index than its parent), and the tree can be a single path.
### Example 1
```text
left = [1, 3, -1, -1, 6, -1, -1]
right = [2, 4, 5, -1, -1, -1, -1]
0
/ \
1 2
/ \ \
3 4 5
/
6
```
Input: `left = [1, 3, -1, -1, 6, -1, -1], right = [2, 4, 5, -1, -1, -1, -1], u = 6, v = 5`
Output: `[6, 4, 1, 0, 2, 5]`
The path climbs from node 6 to the root and then descends to node 5.
### Example 2
Input: the same tree, `u = 3, v = 6`
Output: `[3, 1, 4, 6]`
The path turns at node 1 and never reaches the root.
### Constraints
- `1 <= n == len(left) == len(right) <= 10^5`
- Every child index is `-1` or between `1` and `n - 1`, every node other than `0` is the child of exactly one node, and the links form a single binary tree rooted at node `0`.
- `0 <= u <= n - 1` and `0 <= v <= n - 1` (`u` may equal `v`).
- The tree can be a single path, so its depth can reach `n`.
- Every index fits in a signed 32-bit integer; no value exceeds 2^31 - 1.
Constraints
- 1 <= n == len(left) == len(right) <= 10^5
- Every child index is -1 or between 1 and n - 1, every node other than 0 is the child of exactly one node, and the links form a single binary tree rooted at node 0.
- 0 <= u <= n - 1 and 0 <= v <= n - 1 (u may equal v).
- The tree can be a single path, so its depth can reach n.
- Every index fits in a signed 32-bit integer; no value exceeds 2^31 - 1.
Examples
Input: ([1, 3, -1, -1, 6, -1, -1], [2, 4, 5, -1, -1, -1, -1], 6, 5)
Expected Output: [6, 4, 1, 0, 2, 5]
Explanation: Example 1: the LCA is the root and u, v sit in different subtrees; climb 6-4-1-0, then descend 2-5.
Input: ([1, 3, -1, -1, 6, -1, -1], [2, 4, 5, -1, -1, -1, -1], 3, 6)
Expected Output: [3, 1, 4, 6]
Explanation: Example 2: the LCA is internal node 1, so the path never reaches the root.
Hints
- The examples show the path climbing from u toward the root and then descending to v. At which node does it turn, and how is that node related to u and v?
- Check the cases where one endpoint is an ancestor of the other and where u == v, and make sure the turning node is listed exactly once.
- The tree can be a single path of 10^5 nodes, so consider how deep any recursion in your approach would go.