Katkat
Back

Merge and Serialize N-ary Trees

LinkedInSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Tests recursive tree manipulation, immutable merging semantics, and robust string serialization/deserialization with input validation.

Problem Statement

You are building a hierarchical configuration synchronizer. Configurations are represented as N-ary trees where each node contains:

  • key: a non-empty string identifier unique among siblings
  • val: an integer value
  • children: a list of child Node instances

You need to implement three functions:

  1. merge_trees(t1: Optional[Node], t2: Optional[Node]) -> Optional[Node]: Merges two trees into a new tree without mutating t1 or t2.

    • If one tree is None, return a deep copy of the other.
    • If both trees are non-empty, their root keys must match. If root keys differ, raise a ValueError.
    • For matching nodes, the merged node's val is t1.val + t2.val.
    • Merge children recursively: children with matching keys are merged; children present in only one tree are copied.
    • To ensure deterministic output, each node's children must be sorted alphabetically by key.

  2. serialize(root: Optional[Node]) -> str: Encodes the tree into a deterministic string representation. Return "#" for None. For a valid node, format it as key:val[child1,child2,...] where children are recursively serialized and sorted alphabetically by key.

  3. deserialize(data: str) -> Optional[Node]: Decodes the serialized string back into an N-ary tree. Raises ValueError if data is malformed (e.g., mismatched brackets, invalid integers, duplicate sibling keys, or trailing characters).

Interface

from typing import List, Optional

class Node:
    def __init__(self, key: str, val: int, children: Optional[List['Node']] = None):
        self.key = key
        self.val = val
        self.children = children if children is not None else []

def merge_trees(t1: Optional[Node], t2: Optional[Node]) -> Optional[Node]:
    pass

def serialize(root: Optional[Node]) -> str:
    pass

def deserialize(data: str) -> Optional[Node]:
    pass

Examples

Example 1

# t1: root:5 [a:2, b:3]
# t2: root:10 [b:4, c:1]
merged = merge_trees(t1, t2)
# merged: root:15 [a:2, b:7, c:1]

s = serialize(merged)
# Output: "root:15[a:2[],b:7[],c:1[]]"

node = deserialize(s)
# Round-trip check: serialize(node) == s

Example 2

t1 = Node("A", 1)
t2 = Node("B", 2)
merge_trees(t1, t2)  # Raises ValueError: root keys do not match

Constraints

  • Number of nodes in any tree: 0 <= N <= 10^4
  • Node key: alphanumeric string, 1 <= len(key) <= 32
  • Node val: -10^6 <= val <= 10^6
  • Maximum tree depth: <= 1000

Hints

Hint 1

For merging without mutation, use a recursive helper that constructs new Node objects, grouping children by their keys via a hash map or two-pointer merge over sorted child lists.

Hint 2

For serialization, recursion produces a clean canonical string; make sure you process children in sorted key order.

Hint 3

For deserialization, use an index pointer or parser token stream to parse `key`, `:`, `val`, and handle nested bracketed children with explicit validation checks.

Follow-up questions

  • How would you handle merge conflicts if two nodes have metadata requiring distinct resolution strategies (e.g., last-write-wins vs. max value) instead of summation?
  • If trees exceed memory limits and must be streamed from disk, how would you redesign the merge and serialization pipeline?
  • How can you avoid recursion depth limits when dealing with degenerate trees of depth up to 10^5?