Course4all
Join us on telegram
Home/dsa/Trees/Serialize and Deserialize N-ary Tree

Serialize and Deserialize N-ary Tree

Master this topic with zero to advance depth.

Serialize and Deserialize N-ary Tree

N-ary tree.

Hard
Approach 1

Level I: BFS (Level Order with null markers)

Intuition

In an N-ary tree, we can use a marker (like null) to distinguish between the children of different parents. During serialization, we use a queue and for every node, we add its children followed by a null to indicate the end of that node's children list.

Logic

  • Serialize: Queue based BFS. Append null after children of each node.
  • Deserialize: Use two queues or pointers to rebuild.
⏱ O(N)💾 O(N)

Detailed Dry Run

Node 1 children: [3, 2, 4]. Serialized: [1, null, 3, 2, 4, null, 5, 6, null...]

java
public class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        List<String> res = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        q.add(root); q.add(null);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node == null) {
                res.add("#");
                continue;
            }
            res.add(String.valueOf(node.val));
            for (Node child : node.children) q.add(child);
            q.add(null);
        }
        return String.join(",", res);
    }
}
Approach 2

Level II: DFS (with Parentheses)

Intuition

We can represent the tree structure using parentheses: 1(3(5,6),2,4). This is a very intuitive human-readable format.

Logic

  • Serialize: node.val + ( + serialize(child) for each child + ).
  • Deserialize: Use a stack to track parent nodes and nested parentheses.
⏱ O(N)💾 O(H)

Detailed Dry Run

Tree: 1 -> [3, 2, 4]. 3 -> [5, 6]. Serial: 1(3(5,6),2,4).

java
public class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }
    private void dfs(Node node, StringBuilder sb) {
        sb.append(node.val);
        if (node.children.isEmpty()) return;
        sb.append("(");
        for (int i = 0; i < node.children.size(); i++) {
            dfs(node.children.get(i), sb);
            if (i < node.children.size() - 1) sb.append(",");
        }
        sb.append(")");
    }
}
Approach 3

Level III: Optimal (DFS with Child Count)

Intuition

To serialize an N-ary tree, we can use DFS (Preorder). For each node, we record its value and the number of children it has. During deserialization, we read the value, create a node, and then recursively deserialize exactly count children for that node.

Logic

  • Serialization: Append val and children.size().
  • Deserialization: Read val, read size, then loop size times to build child subtrees.
⏱ O(N)💾 O(N)

Detailed Dry Run

NodeChildrenSerialized Array
13[1, 3]
32[1, 3, 3, 2]
50[1, 3, 3, 2, 5, 0]
60[1, 3, 3, 2, 5, 0, 6, 0]
java
public class Codec {
    public String serialize(Node root) {
        List<String> list = new ArrayList<>();
        buildString(root, list);
        return String.join(",", list);
    }
    private void buildString(Node node, List<String> list) {
        if (node == null) return;
        list.add(String.valueOf(node.val));
        list.add(String.valueOf(node.children.size()));
        for (Node child : node.children) buildString(child, list);
    }
    public Node deserialize(String data) {
        if (data.isEmpty()) return null;
        Deque<String> deque = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(deque);
    }
    private Node buildTree(Deque<String> deque) {
        Node node = new Node(Integer.parseInt(deque.poll()), new ArrayList<>());
        int size = Integer.parseInt(deque.poll());
        for (int i = 0; i < size; i++) node.children.add(buildTree(deque));
        return node;
    }
}
← Previous QuestionCount Univalue Subtrees
Next Question →Lowest Common Ancestor III