Merge two n-ary trees by child position: Frontier Interview's solution

Question: Merge two n-ary trees by child position

Companies: Microsoft

Difficulty: Medium

Problem statement

Implement merge_trees(root1, root2). It takes the roots of two n-ary trees and returns the root of a new tree that merges them.

Each node has an integer val and an ordered list children:

class TreeNode:
    val: int
    children: list[TreeNode]

Nodes are matched by position: the roots match, and the child at index i of a matched pair matches the child at index i of the other node.

If both trees have a node at a position, the merged node's value is the sum of the two values.
If only one tree has a node at a position, the merged tree contains a copy of that whole subtree.
The result must not share any node objects with the inputs. Do not modify the inputs.

Either root may be None. If both are None, return None.

Constraints

Each tree has 0 to 10^5 nodes, and a tree can be up to 10^5 levels deep.
Node values are in [-10^4, 10^4].

Example 1

Tree A:        Tree B:
    1              2
   / \           / | \
  3   2         1  3  7
  |            / \    |
  5           4   6   8

Merged:
      3
   /  |  \
  4   5   7
 / \      |
9   6     8

The roots give 1 + 2 = 3. Child 0 gives 3 + 1 = 4, and its children give 5 + 4 = 9 and a copy of 6. Child 1 gives 2 + 3 = 5. Child 2 exists only in B, so its subtree 7 -> 8 is copied.

Example 2

merge_trees(None, TreeNode(4, [TreeNode(-1)])) returns a new tree 4 -> -1. Changing the result does not change the input tree.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is LeetCode 617 (Merge Two Binary Trees) with a list of children
instead of left and right. Two nodes "overlap" when they are reached by
the same path of child indices from the roots. The merge works one position
at a time:

If both nodes exist, the merged node's value is a.val + b.val. Its
children are the merges of a.children[i] and b.children[i] for every
i up to max(len(a.children), len(b.children)).
If only one node exists, the merged tree gets a copy of that whole
subtree.
If neither exists, there is nothing to do.

Brute force to avoid. Some people first collect both trees into maps
from path to value (for example (0, 2, 1) -> 7), add the maps together,
and rebuild the tree. That is correct, but every path key costs O(depth),
so the total is O(n * depth) time and space. The direct recursion does the
same work in O(n).

Why copy instead of reusing the subtree? The LeetCode binary version
returns the non-null subtree as it is. That shares nodes between the result
and the inputs, so a later change to root1 silently changes the merged
tree. The problem says to return a new tree, so we clone. Say this choice
out loud: it is the first thing interviewers check.

Invariants.

Each merged node at path p has a value equal to the sum of the values
that exist at path p in the inputs.
len(merged.children) == max(len(a.children), len(b.children)). Child
order is kept, because the alignment is by index.
No node in the output is an object from either input.

Recursion depth. A degenerate tree (a chain of 10^5 nodes) overflows
Python's default recursion limit. The code below uses an explicit stack. It
creates each output node before it fills in the node's children. The
recursive version is shorter and fine to write first. Then mention the
stack version, or write it if the interviewer asks about deep trees.

Code

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Optional


@dataclass
class TreeNode:
    val: int
    children: list[TreeNode] = field(default_factory=list)


def merge_trees_recursive(a: Optional[TreeNode], b: Optional[TreeNode]) -> Optional[TreeNode]:
    """Short version. Depth is limited by Python's recursion limit."""
    if a is None and b is None:
        return None
    if a is None or b is None:
        return clone(a or b)
    width = max(len(a.children), len(b.children))
    kids = [
        merge_trees_recursive(
            a.children[i] if i < len(a.children) else None,
            b.children[i] if i < len(b.children) else None,
        )
        for i in range(width)
    ]
    return TreeNode(a.val + b.val, kids)


def clone(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """Deep copy with an explicit stack."""
    if root is None:
        return None
    out = TreeNode(root.val)
    stack = [(root, out)]
    while stack:
        src, dst = stack.pop()
        for child in src.children:
            copy = TreeNode(child.val)
            dst.children.append(copy)
            stack.append((child, copy))
    return out


def merge_trees(a: Optional[TreeNode], b: Optional[TreeNode]) -> Optional[TreeNode]:
    """Iterative merge. Returns a new tree that shares no nodes with a or b."""
    if a is None or b is None:
        return clone(a or b)
    out = TreeNode(a.val + b.val)
    stack: list[tuple[TreeNode, TreeNode, TreeNode]] = [(a, b, out)]
    while stack:
        x, y, dst = stack.pop()
        width = max(len(x.children), len(y.children))
        for i in range(width):
            cx = x.children[i] if i < len(x.children) else None
            cy = y.children[i] if i < len(y.children) else None
            if cx is not None and cy is not None:
                node = TreeNode(cx.val + cy.val)
                stack.append((cx, cy, node))
            else:
                node = clone(cx or cy)  # exactly one side exists
            dst.children.append(node)
    return out


def to_tuple(root: Optional[TreeNode]) -> object:
    """(val, [children...]) form, handy for asserts."""
    if root is None:
        return None
    return (root.val, [to_tuple(c) for c in root.children])


if __name__ == "__main__":
    T = TreeNode
    t1 = T(1, [T(3, [T(5)]), T(2)])
    t2 = T(2, [T(1, [T(4), T(6)]), T(3), T(7, [T(8)])])
    want = (3, [(4, [(9, []), (6, [])]), (5, []), (7, [(8, [])])])
    assert to_tuple(merge_trees(t1, t2)) == want
    assert to_tuple(merge_trees_recursive(t1, t2)) == want

    assert merge_trees(None, None) is None
    assert to_tuple(merge_trees(None, T(4, [T(-1)]))) == (4, [(-1, [])])

    # Result shares no nodes with the inputs.
    m = merge_trees(t1, None)
    m.children[0].val = 100
    assert t1.children[0].val == 3

    # Deep chain: no RecursionError.
    deep = T(0)
    cur = deep
    for i in range(1, 200_000):
        cur.children.append(T(1))
        cur = cur.children[0]
    merged = merge_trees(deep, T(5))
    assert merged.val == 5 and merged.children[0].val == 1
    print("ok")

Complexity

Let n1 and n2 be the node counts and h the height of the result.

Time: O(n1 + n2). Each output node is created once, and each input
node is read once. The output has at most n1 + n2 nodes.
Space: O(n1 + n2) for the new tree, which the problem requires. The
extra working space is the stack. The recursive version uses O(h) call
frames. The iterative version holds pending nodes, at most O(n) in the
worst case and usually much less.
clone: O(size of subtree) time, with the same stack bound.

Test cases

Both empty: merge(None, None) -> None.
One empty: merge(None, 4[-1]) -> a copy 4[-1]. Changing the
result does not change the input.
Single nodes: merge(1, 2) -> 3 with no children.
Different widths: 1[3, 2] and 2[1, 3, 7] -> 3[4, 5, 7]. The third
child comes only from the second tree.
Different depths: 1[3[5]] and 2[1[4, 6]] -> 3[4[9, 6]].
Full example from the code: 1[3[5], 2] and 2[1[4, 6], 3, 7[8]] ->
3[4[9, 6], 5, 7[8]].
Negative and zero values: 0[-2] and 0[2] -> 0[0]. A node with value
0 stays in the tree. A zero sum never removes a node.
A chain of 200,000 nodes merged with a single node: no recursion error,
and the result is the chain with the root value raised by 5.
A wide root (10^5 children) merged with a root that has 1 child: only
index 0 gets a summed child. The rest are copies.

Follow-ups

Merge in place (no new tree). Write into root1. Sum the values,
merge the shared indices, and append root2.children[len(root1.children):].
This uses O(1) extra space for nodes. State the aliasing risk: root1
now shares subtrees with root2, unless you clone the appended part.
Align children by key, not by index. Each child has a name
(like a file system or a config tree). Build a dict from name to child
for one side, then walk the other. Keep a stable order: first a's
order, then the names that exist only in b. The cost stays linear,
with hashing. Ask what happens with duplicate names under one parent.
Merge k trees. Merge many trees at one position at once. Sum the
values of the nodes that exist there. For child i, recurse on the list
of nodes that have an i-th child. This is O(total nodes) in one pass.
Merging the trees two at a time would rebuild the shared parts again and
again.
Another combine rule. Use a function combine(x, y), such as max,
"B overwrites A", or a conflict callback. If the rule can delete a node
(for example, a sum of 0 means remove it), say what happens to its
children: drop them or move them up.
Serialized input. The trees come as level-order arrays with None
separators between child groups (the LeetCode N-ary format). Either
deserialize, merge, and serialize, or merge the two arrays in one BFS
pass, using two queues that advance child group by child group.

Interviewer expectations

Mid-level (L4)

States the rules clearly, including the "only one side exists" case.
Writes the recursive solution with correct bounds on the shorter children
list.
Covers the empty and single-node cases. Gives O(n1 + n2) time.
Notices or accepts the hint that the result should copy subtrees, not
share them.

Senior (L5)

Brings up the copy-versus-share question without a hint. Explains why
it matters (inputs changed later, ownership).
Knows the recursion-depth limit for skewed trees and turns the solution
into an explicit stack.
Changes the code quickly for in-place merge or key-based alignment, with
a clear rule for child order.

Staff (L6+)

Presents index alignment as one point in a design space: index, key, or
content diff. Describes when each fits, for example config overlays,
file trees, or JSON merge-patch.
Generalizes to k-way merges and pluggable combine or conflict rules.
Discusses deletion semantics and keeping the result deterministic.
Considers huge or remote trees: streaming the merge over serialized
input, persistent or structurally shared outputs when the inputs are
immutable, and how to test the merge (round-trip properties, merge with an
empty tree is identity, commutativity under sum).