Flatten a Linked List with Nested Side Branches into One Doubly Linked List

A singly linked list becomes a doubly linked list once every node also links back to its predecessor. This problem extends that conversion. Besides its forward link, any node may carry at most one side branch: a link to the first node of another list. Nodes inside a branch list may carry side branches of their own, so the whole structure is shaped like a binary tree whose root is the head of the main list.

Flatten the structure into one doubly linked list by splicing every side branch in between its parent node and the node that originally followed the parent. Branches nested inside a branch are spliced in the same way, before the rest of the enclosing branch continues.

The nodes are stored in two arrays. Nodes are labeled 0 to n - 1, and node 0 is the head of the main list. next_node[i] is the node that follows node i in its own list, or -1 if node i is the last node of its list. branch[i] is the first node of node i's side branch, or -1 if node i has no side branch.

Return the flattened doubly linked list as two arrays of length n: result[0][i] is the node that comes after node i in the flattened list (-1 for the last node), and result[1][i] is the node that comes before node i (-1 for node 0).

Function Signature

def flatten_with_branches(next_node: list[int], branch: list[int]) -> list[list[int]]:

Rules

• In the flattened list, every node is immediately followed by the flattened contents of its side branch, if it has one, and after that by the flattened remainder of the list that originally followed it.
• Node 0 is the first node of the flattened list, and every node appears in it exactly once.
• If no node has a side branch, the flattened list is the main list in its original order, now with backward links. This is the plain singly-to-doubly conversion.
• Side branches do not appear in the output: after flattening, nodes are connected only by their forward and backward links.
• Return exactly two arrays: forward links first, backward links second.

Constraints

• 1 <= n <= 100000, where n = len(next_node) = len(branch)
• -1 <= next_node[i] <= n - 1 and -1 <= branch[i] <= n - 1
• Node 0 is referenced by no entry of next_node or branch. Every other node is referenced by exactly one entry across the two arrays, and every node can be reached from node 0 by following next_node and branch links. The structure therefore has no cycles and no shared nodes.
• Branches may be nested, and the nesting depth can be as large as n - 1.
• The output is uniquely determined by the input.

Examples

Example 1

• Input: next_node = [1, 2, -1], branch = [-1, -1, -1]
• Output: [[1, 2, -1], [-1, 0, 1]]
• Explanation: There are no side branches. The list 0 -> 1 -> 2 keeps its order and gains backward links.

Example 2

• Input: next_node = [1, 2, -1, 4, -1, -1], branch = [-1, 3, -1, 5, -1, -1]
• Output: [[1, 3, -1, 5, 2, 4], [-1, 0, 4, 1, 5, 3]]
• Explanation: The main list is 0 -> 1 -> 2. Node 1 has the side branch 3 -> 4, and node 3 has the side branch 5. The flattened list is 0 -> 1 -> 3 -> 5 -> 4 -> 2: node 3's branch comes right after node 3, then the rest of node 1's branch (node 4), then the rest of the main list (node 2).

Example 3

• Input: next_node = [1, -1, 3, -1], branch = [-1, 2, -1, -1]
• Output: [[1, 2, 3, -1], [-1, 0, 1, 2]]
• Explanation: Node 1 is the last node of the main list and has the side branch 2 -> 3, so the branch simply extends the list: 0 -> 1 -> 2 -> 3.

Flatten a Branching List into a Doubly Linked List

Hints

1. Treat branch[i] as a left child and next_node[i] as a right child. In what traversal order does the flattened list visit the nodes?
2. Once you know the visiting order, the forward and backward links are just consecutive pairs in that order.
3. Nesting can be n - 1 levels deep, so a recursive walk can overflow the call stack. Which data structure lets you do the same walk iteratively?

Approach

If branch[i] is read as the left child of node i and next_node[i] as its right child, the structure is a binary tree rooted at node 0. The rules say a node is followed first by its whole flattened side branch and only then by the flattened remainder of its own list, which is exactly a preorder traversal: visit the node, then its left subtree, then its right subtree. The reference performs that preorder walk with an explicit stack instead of recursion, because the nesting depth (and the length of a list) can reach n - 1, which would overflow the call stack in most languages. It pops a node, links it to the previously visited node (forward[prev] = node and backward[node] = prev), then pushes next_node[node] before branch[node] so that the side branch is popped, and therefore visited, first. Node 0 is visited first, so backward[0] stays -1, and the last node visited keeps forward = -1. Every node is pushed and popped exactly once, because each non-head node is referenced by exactly one link.

• Time complexity: O(n)
• Space complexity: O(n)