Quick Overview

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

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.

Quick Answer: 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

  1. 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.
  2. A recursive solution is natural, but an explicit stack is safer in Python because the tree can be very deep.

Loading coding console...