Serialize and Deserialize N-ary Tree

Hard Trees & BST Tree Serialization / Deserialization Original on LeetCode

Reported atMicrosoft

Serialize and Deserialize N-ary Tree is a hard trees & bst problem solved with the tree serialization / deserialization pattern. The best approach, optimal (preorder with child counts), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from level order with end markers up.

Problem

An N-ary tree is a rooted tree in which each node has a value val and a list children of any length. Design a Codec with two methods: serialize(root) turns such a tree into a string, and deserialize(data) turns that string back into a tree identical to the original (same values, same children in the same order).

You choose the string format. The only requirement is that deserialize(serialize(root)) reproduces the tree exactly, and neither method may rely on fields or globals left over from earlier calls.

Examples

Example 1

Input
root = [7, null, 2, 9, 4, null, 1, 8, null, null, 6]
Output
deserialize(serialize(root)) gives the same tree
Why
The input lists the tree level by level, with null closing each node's group of children: 7 has children 2, 9, 4; 2 has children 1, 8; 9 has none; 4 has child 6. One possible string is "7,3,2,2,1,0,8,0,9,0,4,1,6,0" (value, child count, in preorder).

Example 2

Input
root = [5]
Output
[5]
Why
A single node with no children.

Example 3

Input
root = []
Output
[]
Why
The empty tree must survive the round trip too, for example as the empty string.

Constraints

  • The tree has 0 to 10^4 nodes.
  • 0 <= Node.val <= 10^4
  • The height of the tree is at most 1000.
  • A node may have any number of children. serialize and deserialize must not keep state between calls.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Level order with end markersO(n)O(n)
Optimal (preorder with child counts)O(n)O(n)

1Level order with end markers

TimeO(n)Every node is written once and read once, plus one '#' per node.
SpaceO(n)The string, the token array and the BFS queue are all O(n).

Write the root, then process nodes in BFS order: for each node write all its children's values followed by a # marking the end of that node's children. To rebuild, read the root, then for each node taken from a queue read values until the next #; those are its children, in order.

  1. serialize: if root is null return "". Write root.val; BFS: for each polled node write each child's value (and enqueue it), then write '#'.
  2. deserialize: if the string is empty return null. Split on ','; the first token is the root.
  3. For each node polled from the queue: create a child for every token until '#', add it to the node's children and enqueue it; skip the '#'.
class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val).append(',');
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.children != null) {
                for (Node c : node.children) {
                    sb.append(c.val).append(',');
                    q.add(c);
                }
            }
            sb.append("#,");
        }
        return sb.toString();
    }

    public Node deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] t = data.split(",");
        Node root = new Node(Integer.parseInt(t[0]), new ArrayList<>());
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty()) {
            Node node = q.poll();
            while (!t[i].equals("#")) {
                Node c = new Node(Integer.parseInt(t[i]), new ArrayList<>());
                node.children.add(c);
                q.add(c);
                i++;
            }
            i++; // skip '#'
        }
        return root;
    }
}

2Optimal (preorder with child counts)

TimeO(n)Two tokens per node, each written once and read once.
SpaceO(n)The string and tokens are O(n); the recursion depth is the tree height (at most 1000).

Write each node as two tokens, its value and its number of children, in preorder. Reading is a mirror image: read a value and a count, then recursively read exactly that many subtrees as its children. No markers or queue are needed, and the string is as short as the BFS one.

  1. serialize: if root is null return "". write(node): append val and children.size(), then write every child.
  2. deserialize: if empty return null. Split into tokens and keep a read position.
  3. read(): val = next token, count = next token; create the node; call read() count times and append the results as children; return the node.
class Codec {
    private int pos;

    public String serialize(Node root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }

    private void write(Node node, StringBuilder sb) {
        int count = node.children == null ? 0 : node.children.size();
        sb.append(node.val).append(',').append(count).append(',');
        for (int k = 0; k < count; k++) {
            write(node.children.get(k), sb);
        }
    }

    public Node deserialize(String data) {
        if (data.isEmpty()) return null;
        pos = 0;
        return read(data.split(","));
    }

    private Node read(String[] t) {
        int val = Integer.parseInt(t[pos++]);
        int count = Integer.parseInt(t[pos++]);
        Node node = new Node(val, new ArrayList<>());
        for (int k = 0; k < count; k++) {
            node.children.add(read(t));
        }
        return node;
    }
}

Edge cases to test

  • Empty tree
  • A root with many children and no grandchildren (very wide)
  • A single long chain of one child each (very deep)
  • Leaves at different depths, so the format must record where each node's children end

Hints

Hint 1

With a binary tree you could write null for missing children. Here the number of children varies, so you need another way to know where a child list ends.

Hint 2

Either write an end marker after every node's children, or write the number of children next to each value.

Hint 3

With the child count stored, a preorder string can be rebuilt with a single recursive read that consumes tokens left to right.

FAQ

What is the best time complexity for Serialize and Deserialize N-ary Tree?

Optimal (preorder with child counts) runs in O(n) time and O(n) extra space. Two tokens per node, each written once and read once.

Which pattern does Serialize and Deserialize N-ary Tree use?

It is a trees & bst problem that uses the tree serialization / deserialization pattern. Other problems with the same pattern: Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Construct Binary Search Tree from Preorder Traversal.

Is there a brute force solution for Serialize and Deserialize N-ary Tree?

Yes. Level order with end markers takes O(n) time and O(n) space. Write the root, then process nodes in BFS order: for each node write all its children's values followed by a marking the end of that node's children.

Which edge cases should I test for Serialize and Deserialize N-ary Tree?

Empty tree; A root with many children and no grandchildren (very wide); A single long chain of one child each (very deep); Leaves at different depths, so the format must record where each node's children end.