Merge Hierarchical Trees by Name

Two ordered rooted trees are encoded by parallel names, values, and parents arrays. Nodes are listed in preorder. The root is index 0 with parent -1; each later parent index is smaller than its child index. Sibling order is their order in the arrays.
Merge the two roots. A merged node takes its name from the first tree and its value from the second tree. For each pair of merged parents, children with the same name are paired in occurrence order and merged recursively.
Keep every child from the first tree in its original order.
Copy an unmatched first-tree child with its complete subtree unchanged.
After those children, append every unmatched second-tree child with its complete subtree in its original order.
Return the merged tree in preorder. Encode each node as depth:name:value, where the root depth is 0.

Function
mergeHierarchies(names1: String[], values1: int[], parents1: int[], names2: String[], values2: int[], parents2: int[]) → String[]

Examples
Example 1
names1 = ["root","a","x","a"]
values1 = [1,2,3,4]
parents1 = [-1,0,1,0]
names2 = ["other","a","y","a","z","b"]
values2 = [10,20,30,40,50,60]
parents2 = [-1,0,1,0,3,0]
return = ["0:root:10","1:a:20","2:x:3","2:y:30","1:a:40","2:z:50","1:b:60"]
The first and second a children pair by occurrence. Unmatched first-tree children remain before unmatched second-tree children, and the second-tree b child is appended last.
Example 2
names1 = ["r","left"]
values1 = [1,2]
parents1 = [-1,0]
names2 = ["r2","right"]
values2 = [9,8]
parents2 = [-1,0]
return = ["0:r:9","1:left:2","1:right:8"]
The root uses the first root's name and second root's value. Its differently named children remain in first-tree then second-tree order.

Constraints
1 <= names1.length, names2.length <= 2000.
Within each tree, the three parallel arrays have equal lengths.
Nodes are listed in preorder; parents[0] == -1 and 0 <= parents[i] < i for i > 0.
Every name contains lowercase English letters, has length from 1 through 30, and contains no colon.
Node values fit in a signed 32-bit integer.
Tree depth is at most 500.

Build child lists from the parents arrays first. Each node gets an ordered list of child indices, which is easy because parents always point backward. Then recurse on a pair of nodes. For the merged pair, emit depth:name1:value2. For children, group tree two's children by name into queues, preserving order. Walk tree one's children in order. If a queue for that name has an entry, pop it and recurse on the pair. Otherwise copy the subtree unchanged. After that, append every tree two child that was never popped, each with its full subtree. The pitfall is using a plain map from name to child, which breaks on the duplicate a children in Example 1. Another is forgetting depth is relative to the merged output. Depth is at most 500, so watch recursion limits. StealthCoder is the hedge if the queue idea doesn't come to you under pressure.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.