Merge N-Ary Trees by Key

Two immutable rooted N-ary trees are encoded by keys1, parents1, keys2, and parents2. For either tree, keys[i] is the key of node i. The root is node 0 and has parent -1; every later node has a parent index smaller than its own index.
Perform one sequential merge. The roots have the same key and become one root. Under two already-merged parent nodes, children with the same key become one child and their descendants are merged by the same rule. A child key that appears under only one of those parents is copied with its entire subtree. Equal keys under different parent paths are different nodes and do not merge.
Return a canonical description of the merged tree as every root-to-node key path, including the root path. Join adjacent keys in a path with /, then return all paths in lexicographic order.

Function
mergeNaryTrees(keys1: String[], parents1: int[], keys2: String[], parents2: int[]) → String[]

Examples
Example 1
keys1 = ["a","b","d","c"]
parents1 = [-1,0,1,0]
keys2 = ["a","b","e","d"]
parents2 = [-1,0,1,0]
return = ["a","a/b","a/b/d","a/b/e","a/c","a/d"]
The two a/b nodes merge because both their parent path and key match. Their children d and e are both retained. The root children c and d occur in only one input tree.
Example 2
keys1 = ["r","a","x","b","k"]
parents1 = [-1,0,1,0,3]
keys2 = ["r","a","k","b","x"]
parents2 = [-1,0,1,0,3]
return = ["r","r/a","r/a/k","r/a/x","r/b","r/b/k","r/b/x"]
Keys k and x each occur below both a and b across the two trees. They stay separate because matching is relative to already-merged parent nodes.

Constraints
1 <= keys1.length, keys2.length <= 2000
keys1.length == parents1.length and keys2.length == parents2.length.
Each key contains only lowercase English letters and has length from 1 through 20.
For each tree, parents[0] == -1, and 0 <= parents[i] < i for every i > 0.
Children of the same parent have distinct keys.
keys1[0] == keys2[0].
The total length of all returned path strings fits in memory.

Build children maps for each tree: node index to a map of key to child index. Then recurse from the two roots together. At each merged pair, take the union of child keys. If a key exists in both, recurse with both child indices. If it exists in only one, recurse with the other side set to -1 so the whole subtree gets copied. Build the path string as you go and add it to a result list. Sort at the end. The edge case that breaks naive solutions is example 2: keys k and x appear under both a and b, and a global key-to-node map would wrongly fuse them. Matching must be relative to the merged parent, never by key alone. Depth can reach 2000, so watch recursion limits or go iterative. StealthCoder is your hedge on the live OA if the recursion with a missing side gets tangled.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.