# Merge Keyed N-Ary Trees An N-ary tree node contains a unique string `key` among its siblings and a list of children. Implement `merge_trees(a, b)` for two roots with the same key. Nodes at the same parent are merged only when their keys match. Matching nodes are merged recursively. A child present in only one tree is retained unchanged. Preserve the first tree's child order; append children whose keys appear only in the second tree in their original order. The function must return a new tree and must not mutate either input. ## Constraints - Each sibling list contains no duplicate key. - The two root keys are equal. - The total number of nodes across both inputs is at most `200000`. - Tree depth may be large, so identify how recursion depth is handled. ## Example If root `r` has children `[a(children=[x]), b]` in the first tree and `[a(children=[y]), c]` in the second, the merged root has children `[a(children=[x, y]), b, c]`. ## Clarifications Keys define identity only within the same parent. Equal keys in unrelated branches do not merge. Discuss expected time and space complexity and the data structure used to avoid repeatedly scanning sibling lists. ## Hints At each merged parent, an index from child key to output position can turn repeated matching into direct lookup. ## Extensions - How would you merge several trees concurrently without corrupting shared state? - Compare coarse locks, per-node locks, immutable snapshots, and MVCC for a shared version. - How would conflicting payload values be resolved if nodes also stored data?