Serialize and Deserialize N-ary Tree
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
0to10^4nodes. 0 <= Node.val <= 10^4- The height of the tree is at most
1000. - A node may have any number of children.
serializeanddeserializemust 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.
| Approach | Time | Space |
|---|---|---|
| Level order with end markers | O(n) | O(n) |
| Optimal (preorder with child counts) | O(n) | O(n) |
1Level order with end markers
O(n)Every node is written once and read once, plus one '#' per node.O(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.
- serialize: if root is null return "". Write root.val; BFS: for each polled node write each child's value (and enqueue it), then write '#'.
- deserialize: if the string is empty return null. Split on ','; the first token is the root.
- 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;
}
}class Codec:
def serialize(self, root: 'Optional[Node]') -> str:
if root is None:
return ""
out = [str(root.val)]
q = deque([root])
while q:
node = q.popleft()
for c in node.children or []:
out.append(str(c.val))
q.append(c)
out.append("#")
return ",".join(out)
def deserialize(self, data: str) -> 'Optional[Node]':
if not data:
return None
t = data.split(",")
root = Node(int(t[0]), [])
q = deque([root])
i = 1
while q:
node = q.popleft()
while t[i] != "#":
c = Node(int(t[i]), [])
node.children.append(c)
q.append(c)
i += 1
i += 1 # skip '#'
return rootclass Codec {
public:
string serialize(Node* root) {
if (!root) return "";
string s = to_string(root->val) + ",";
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
for (Node* c : node->children) {
s += to_string(c->val) + ",";
q.push(c);
}
s += "#,";
}
return s;
}
Node* deserialize(string data) {
if (data.empty()) return nullptr;
vector<string> t;
string cur;
for (char ch : data) {
if (ch == ',') {
t.push_back(cur);
cur.clear();
} else {
cur += ch;
}
}
Node* root = new Node(stoi(t[0]), {});
queue<Node*> q;
q.push(root);
size_t i = 1;
while (!q.empty()) {
Node* node = q.front();
q.pop();
while (t[i] != "#") {
Node* c = new Node(stoi(t[i]), {});
node->children.push_back(c);
q.push(c);
i++;
}
i++; // skip '#'
}
return root;
}
};class Codec {
serialize(root) {
if (root === null) return "";
const out = [String(root.val)];
const q = [root];
for (let h = 0; h < q.length; h++) {
for (const c of q[h].children || []) {
out.push(String(c.val));
q.push(c);
}
out.push("#");
}
return out.join(",");
}
deserialize(data) {
if (data === "") return null;
const t = data.split(",");
const root = new Node(parseInt(t[0], 10), []);
const q = [root];
let i = 1;
for (let h = 0; h < q.length; h++) {
const node = q[h];
while (t[i] !== "#") {
const c = new Node(parseInt(t[i], 10), []);
node.children.push(c);
q.push(c);
i++;
}
i++; // skip '#'
}
return root;
}
}2Optimal (preorder with child counts)
O(n)Two tokens per node, each written once and read once.O(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.
- serialize: if root is null return "". write(node): append val and children.size(), then write every child.
- deserialize: if empty return null. Split into tokens and keep a read position.
- 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;
}
}class Codec:
def serialize(self, root: 'Optional[Node]') -> str:
if root is None:
return ""
out: List[str] = []
self.write(root, out)
return ",".join(out)
def write(self, node: 'Node', out: List[str]) -> None:
kids = node.children or []
out.append(str(node.val))
out.append(str(len(kids)))
for c in kids:
self.write(c, out)
def deserialize(self, data: str) -> 'Optional[Node]':
if not data:
return None
self.t = data.split(",")
self.pos = 0
return self.read()
def read(self) -> 'Node':
val = int(self.t[self.pos])
count = int(self.t[self.pos + 1])
self.pos += 2
node = Node(val, [])
for _ in range(count):
node.children.append(self.read())
return nodeclass Codec {
public:
string serialize(Node* root) {
if (!root) return "";
string s;
write(root, s);
return s;
}
Node* deserialize(string data) {
if (data.empty()) return nullptr;
t.clear();
string cur;
for (char ch : data) {
if (ch == ',') {
t.push_back(cur);
cur.clear();
} else {
cur += ch;
}
}
pos = 0;
return read();
}
private:
vector<string> t;
size_t pos = 0;
void write(Node* node, string& s) {
s += to_string(node->val) + "," + to_string(node->children.size()) + ",";
for (Node* c : node->children) write(c, s);
}
Node* read() {
int val = stoi(t[pos++]);
int count = stoi(t[pos++]);
Node* node = new Node(val, {});
for (int k = 0; k < count; k++) {
node->children.push_back(read());
}
return node;
}
};class Codec {
serialize(root) {
if (root === null) return "";
const out = [];
const write = (node) => {
const kids = node.children || [];
out.push(String(node.val), String(kids.length));
for (const c of kids) write(c);
};
write(root);
return out.join(",");
}
deserialize(data) {
if (data === "") return null;
const t = data.split(",");
let pos = 0;
const read = () => {
const val = parseInt(t[pos++], 10);
const count = parseInt(t[pos++], 10);
const node = new Node(val, []);
for (let k = 0; k < count; k++) node.children.push(read());
return node;
};
return read();
}
}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.