How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at LinkedIn during technical interviews.

Merge two N-ary trees by key rules | LinkedIn Coding Question

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.

Input: ({'key': 'r', 'value': 0, 'children': [{'key': 'a', 'value': 1, 'children': [{'key': 'm', 'value': 5, 'children': []}]}, {'key': 'd', 'value': 4, 'children': []}]}, {'key': 'r', 'value': 9, 'children': [{'key': 'a', 'value': 10, 'children': [{'key': 'n', 'value': 6, 'children': []}]}, {'key': 'c', 'value': 3, 'children': [{'key': 'z', 'value': 7, 'children': []}]}]})

Expected Output: {'key': 'r', 'value': 9, 'children': [{'key': 'a', 'value': 10, 'children': [{'key': 'm', 'value': 5, 'children': []}, {'key': 'n', 'value': 6, 'children': []}]}, {'key': 'd', 'value': 4, 'children': []}, {'key': 'c', 'value': 3, 'children': [{'key': 'z', 'value': 7, 'children': []}]}]}

Explanation: Child 'a' appears in both trees, so it is merged and takes value 10 from tree_b. Its child 'm' comes only from tree_a and 'n' comes only from tree_b. Child 'd' is copied from tree_a and child 'c' is appended from tree_b.

Input: ({'key': 'root', 'value': 0, 'children': [{'key': 'alpha', 'value': 1, 'children': [{'key': 'k', 'value': 100, 'children': []}]}, {'key': 'beta', 'value': 2, 'children': []}]}, {'key': 'root', 'value': 99, 'children': [{'key': 'beta', 'value': 20, 'children': [{'key': 'p', 'value': 8, 'children': []}]}, {'key': 'alpha', 'value': 10, 'children': [{'key': 'k', 'value': 101, 'children': []}, {'key': 'q', 'value': 9, 'children': []}]}, {'key': 'gamma', 'value': 30, 'children': []}]})

Expected Output: {'key': 'root', 'value': 99, 'children': [{'key': 'alpha', 'value': 10, 'children': [{'key': 'k', 'value': 101, 'children': []}, {'key': 'q', 'value': 9, 'children': []}]}, {'key': 'beta', 'value': 20, 'children': [{'key': 'p', 'value': 8, 'children': []}]}, {'key': 'gamma', 'value': 30, 'children': []}]}

Explanation: The matching children are found by key, not by index. Even though tree_b lists 'beta' before 'alpha', the output preserves the deterministic order rule based on tree_a first, then tree_b-only children.

Input: ({'key': 'root', 'value': 1, 'children': [{'key': 'a', 'value': 2, 'children': [{'key': 'b', 'value': 3, 'children': [{'key': 'c', 'value': 4, 'children': []}]}]}]}, {'key': 'root', 'value': 10, 'children': [{'key': 'a', 'value': 20, 'children': [{'key': 'b', 'value': 30, 'children': [{'key': 'd', 'value': 40, 'children': []}, {'key': 'c', 'value': 400, 'children': []}]}]}]})

Expected Output: {'key': 'root', 'value': 10, 'children': [{'key': 'a', 'value': 20, 'children': [{'key': 'b', 'value': 30, 'children': [{'key': 'c', 'value': 400, 'children': []}, {'key': 'd', 'value': 40, 'children': []}]}]}]}

Explanation: This deep case shows recursive merging down multiple levels. Node 'c' exists in both trees and takes value 400 from tree_b, while 'd' exists only in tree_b and is appended after processing tree_a children.

Solution

def solution(tree_a, tree_b):\n    def clone_tree(node):\n        new_root = {'key': node['key'], 'value': node['value'], 'children': []}\n        stack = [(node, new_root)]\n\n        while stack:\n            src, dst = stack.pop()\n            for child in src['children']:\n                copied = {'key': child['key'], 'value': child['value'], 'children': []}\n                dst['children'].append(copied)\n                stack.append((child, copied))\n\n        return new_root\n\n    if tree_a['key'] != tree_b['key']:\n        raise ValueError('Root keys must match')\n\n    merged_root = {'key': tree_a['key'], 'value': tree_b['value'], 'children': []}\n    stack = [(tree_a, tree_b, merged_root)]\n\n    while stack:\n        node_a, node_b, out = stack.pop()\n        b_map = {child['key']: child for child in node_b['children']}\n        a_keys = set()\n\n        for child_a in node_a['children']:\n            key = child_a['key']\n            a_keys.add(key)\n\n            if key in b_map:\n                child_b = b_map[key]\n                merged_child = {'key': key, 'value': child_b['value'], 'children': []}\n                out['children'].append(merged_child)\n                stack.append((child_a, child_b, merged_child))\n            else:\n                out['children'].append(clone_tree(child_a))\n\n        for child_b in node_b['children']:\n            if child_b['key'] not in a_keys:\n                out['children'].append(clone_tree(child_b))\n\n    return merged_root

Time complexity: O(n + m). Space complexity: O(n + m).

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.

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.