List the Nodes on the Path Between Two Nodes of a Binary Tree

Given a binary tree and two of its nodes, return the nodes on the path that connects them.

Function Signature

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:

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

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

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.