Merge two N-ary trees by key rules

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two **N-ary trees** `A` and `B`. Each node has: - `key` (string): unique among siblings (i.e., within a node’s children list, no two children share the same key) - `value` (any scalar, e.g., string/int) - `children` (list of nodes) You must produce a merged tree `M = merge(A, B)` using these rules: ## Merge rules 1. **If a node exists in both trees at the same position (matched by `key`)**: - The merged node’s `key` stays the same. - The merged node’s `value` is **taken from tree `B`** (i.e., `B` overwrites `A`). - The merged node’s `children` are formed by merging children lists by key, recursively. 2. **If a child key exists only in one tree**: - Include that subtree unchanged in the output. Assume the two input roots have the **same key**. ## Task Implement a function to merge the two trees and return the merged root. ## Constraints - Total nodes across both trees: up to `2 * 10^5` - Keys are non-empty strings ## Clarifications - Sibling order in the output does not matter unless you choose to preserve a stable order.

Overview: This question evaluates understanding of N-ary tree data structures, hierarchical merging semantics, and algorithmic reasoning about recursion and key-based child reconciliation.

You are given two non-empty N-ary trees, tree_a and tree_b. Each node is represented as a dictionary with three fields: 'key' (string), 'value' (scalar), and 'children' (list of child nodes). The two roots always have the same key. Merge the trees so that when the same child key appears under the same parent in both trees, the merged node keeps that key, takes its value from tree_b, and recursively merges their children by key. If a child key exists in only one tree, include that entire subtree unchanged. Return a new merged tree without modifying the inputs. For deterministic judging, preserve child order as follows: process tree_a children from left to right first, merging or copying each one, then append children that exist only in tree_b in tree_b's original order.

Constraints

Each tree has at least 1 node, and the two root keys are identical.
Total nodes across both trees is at most 2 * 10^5.
Each key is a non-empty string.
Within any single node's children list, all keys are unique.

Examples

Input: ({'key': 'root', 'value': 1, 'children': [{'key': 'a', 'value': 10, 'children': []}, {'key': 'b', 'value': 20, 'children': [{'key': 'x', 'value': 1, 'children': []}]}]}, {'key': 'root', 'value': 2, 'children': [{'key': 'b', 'value': 200, 'children': [{'key': 'y', 'value': 2, 'children': []}, {'key': 'x', 'value': 9, 'children': []}]}, {'key': 'c', 'value': 30, 'children': []}]})

Expected Output: {'key': 'root', 'value': 2, 'children': [{'key': 'a', 'value': 10, 'children': []}, {'key': 'b', 'value': 200, 'children': [{'key': 'x', 'value': 9, 'children': []}, {'key': 'y', 'value': 2, 'children': []}]}, {'key': 'c', 'value': 30, 'children': []}]}

Explanation: Root value is overwritten by tree_b. Child 'a' exists only in tree_a, child 'c' exists only in tree_b, and child 'b' is merged recursively. Under 'b', 'x' is merged and takes value 9 from tree_b, while 'y' is appended from tree_b.

Input: ({'key': 'r', 'value': 'old', 'children': []}, {'key': 'r', 'value': 'new', 'children': []})

Expected Output: {'key': 'r', 'value': 'new', 'children': []}

Explanation: This edge case has only the root node. The merged root keeps key 'r' and takes its value from tree_b.

Hints

For each pair of matched nodes, build a hash map from child key to child node for one side so you can check matches in O(1) time.
A recursive solution is natural, but an explicit stack is safer in Python because the tree can be very deep.

Approach

Approach: iterative key-keyed tree merge. Both trees are merged structurally by matching child keys under each shared parent. The solution avoids recursion (the tree can have up to 2·10^5 nodes) by using explicit stacks.

Building the root. Since both roots share a key, merged_root is seeded with that key, the value taken from tree_b, and an empty children list. The triple (tree_a, tree_b, merged_root) is pushed onto a work stack.

Per-node merge. For each popped (node_a, node_b, out):

Build b_map = {child_key: child} over node_b's children — O(children) lookup so matching by key is O(1).
Walk node_a's children left to right. If a key also appears in b_map, create a merged child (value from b) and push (child_a, child_b, merged_child) to recurse into their subtrees. Otherwise the key is a-only, so append a deep copy via clone_tree.
Then walk node_b's children and append (cloned) any whose key wasn't in a_keys, in b's original order.

This exactly produces the required deterministic order: a's children first (merged or copied), then b-only children appended.

clone_tree does an iterative stack-based DFS that rebuilds a subtree into fresh dicts, so the inputs are never mutated and the result is fully independent.

Why it's correct: each output node's children list is fully populated at the moment its triple is processed, so the LIFO stack order between siblings doesn't affect the final structure — order is fixed by the append sequence within each node. Values follow the "b wins on conflict" rule, and exclusive subtrees are copied whole.

Time complexity:

O(n + m)

Space complexity: