Merge Two Keyed N-ary Trees

Merge Two Keyed N-ary Trees You are given two N-ary trees. Each node has a unique string key and zero or more children. The root nodes of the two trees have the same key. Merge the trees using these rules: Only nodes with the same key may be merged into one node. For every pair of merged nodes, merge their children by child key: If a child key exists in both trees, recursively merge those two child nodes. If a child key exists in only one tree, preserve that entire subtree unchanged. Return the merged tree. For this programming task, the input format is: Number of nodes n1, followed by n1 node records for the first tree. Number of nodes n2, followed by n2 node records for the second tree. A node record is: key childCount childKey1 childKey2 .... The first node record of each tree is its root. Keys are unique within a tree. Print the merged tree in preorder. Children of every node must be printed in lexicographic order of key. Example Input 4 root 2 a b a 1 x b 0 x 0 4 root 2 a c a 1 y c 0 y 0 Output 6 root 3 a b c a 2 x y x 0 y 0 b 0 c 0 Constraints 1 <= n1, n2 <= 100000 Each key has at most 50 characters. Both inputs are valid trees and their roots have the same key. Avoid recursive implementations that can overflow the call stack on deep trees. Example Input 1 root 0 1 root 0 Output 1 root 0