Katkat
Back

Encode an N-ary tree as a string and decode it back to the identical tree

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Design a string format for rooted N-ary trees and implement serialize and deserialize so the decoded tree has the same values, shape and child order. It tests unambiguous encoding of variable child counts, linear-time parsing, iterative handling of very deep trees, and validation of malformed input.

A rooted N-ary tree is a tree in which each node can have any number of children, kept in a fixed order. Design a string format for such trees and implement both directions:

  • serialize(root) turns a tree into a string.
  • deserialize(data) rebuilds the tree from that string.

Deserializing the output of serialize must reproduce the original tree exactly: the same values, the same shape and the same order of children under every node. The format is yours to choose, but deserialize must work from the string alone, with no state kept between calls.

class Node:
 def __init__(self, val, children=None):
 self.val = val
 self.children = children if children is not None else []

def serialize(root: Node | None) -> str: ...
def deserialize(data: str) -> Node | None: ...

Constraints and Clarifications

  • Assume node values are integers, possibly negative, unless the interviewer says otherwise.
  • The tree may be empty (root is None) or consist of a single node.
  • Child order matters: two trees that differ only in the order of some node's children are different trees.

Clarifying Questions

  • Are values always integers, or can they be arbitrary strings that may contain the characters your format uses as delimiters?
  • How many nodes, how many children per node, and how deep can the tree be?
  • Does the size of the string matter, for example because it is stored or sent over a network, or should it stay human-readable?
  • Should deserialize detect malformed input, or may it assume the string came from serialize?

Hints

Hint 1

Where do the children stop?: In a binary tree every node has exactly two child slots, so writing a marker for each empty slot is enough to recover the shape. Here the number of children varies. Decide what the decoder must learn from the string to know where one node's children end.

Hint 2

Decode in one left-to-right pass: Choose a node order and a token layout that let the decoder consume tokens strictly from left to right, building nodes as it goes, without backtracking.

Follow-up questions

  • Values become arbitrary strings that may contain spaces, commas and brackets. How does your format change?
  • How would you make the encoded form as compact as possible?
  • How would you decode a tree whose depth is one million without exceeding the recursion limit?
  • How would you detect a truncated or corrupted string instead of returning a wrong tree?