Serialize and Deserialize Tree
In this page:
Serialization Idea
Serialization converts a tree structure into a flat, storable sequence (like a string or array) so it can be saved to a file, sent over a network, or cached — trees can't be stored directly in these linear formats without first flattening them.
Example: Serialization Idea
#include <iostream>
#include <string>
using namespace std;
struct Node { int val; Node *left, *right; };
void serialize(Node* n, string& out) {
if (!n) { out += "# "; return; }
out += to_string(n->val) + " ";
serialize(n->left, out);
serialize(n->right, out);
}
int main() {
Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
Node root={1,&l,&r};
string out;
serialize(&root, out);
cout << "Serialized: " << out << endl;
return 0;
}public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
static void serialize(Node n, StringBuilder out) {
if (n == null) { out.append("# "); return; }
out.append(n.val).append(" ");
serialize(n.left, out);
serialize(n.right, out);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
StringBuilder out = new StringBuilder();
serialize(root, out);
System.out.println("Serialized: " + out);
}
}class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
def serialize(n, out):
if n is None:
out.append("#")
return
out.append(str(n.val))
serialize(n.left, out)
serialize(n.right, out)
root = Node(1)
root.left = Node(2); root.right = Node(3)
out = []
serialize(root, out)
print("Serialized:", " ".join(out))#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void serialize(struct Node* n) {
if (!n) { printf("# "); return; }
printf("%d ", n->val);
serialize(n->left);
serialize(n->right);
}
int main() {
struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
struct Node root={1,&l,&r};
printf("Serialized: ");
serialize(&root);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
Null Markers
Because trees can have missing children at arbitrary positions, serialization needs explicit null markers in the output sequence to record exactly where a child is absent — without them, the shape of the original tree would be ambiguous when rebuilding it.
Example: Null Markers
#include <iostream>
using namespace std;
int main() {
cout << "Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it");
}
}print("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it")#include <stdio.h>
int main() {
printf("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it\n");
return 0;
}Login to try C/C++/Java code in the editor
Deserialization
Deserialization reverses the process, reading the flat sequence back and reconstructing the original tree node by node, using the same traversal order and null markers that were used during serialization to know exactly where each node belongs.
Example: Deserialization
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* deserialize(istringstream& in) {
string token; in >> token;
if (token == "#") return nullptr;
Node* n = new Node{stoi(token), nullptr, nullptr};
n->left = deserialize(in);
n->right = deserialize(in);
return n;
}
int main() {
istringstream in("1 2 # # 3 # #");
Node* root = deserialize(in);
cout << "Rebuilt root value: " << root->val << endl;
return 0;
}import java.util.*;
public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
static Scanner sc;
static Node deserialize() {
String token = sc.next();
if (token.equals("#")) return null;
Node n = new Node(Integer.parseInt(token));
n.left = deserialize();
n.right = deserialize();
return n;
}
public static void main(String[] args) {
sc = new Scanner("1 2 # # 3 # #");
Node root = deserialize();
System.out.println("Rebuilt root value: " + root.val);
}
}class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
def deserialize(tokens):
token = next(tokens)
if token == "#":
return None
n = Node(int(token))
n.left = deserialize(tokens)
n.right = deserialize(tokens)
return n
data = "1 2 # # 3 # #"
root = deserialize(iter(data.split()))
print("Rebuilt root value:", root.val)#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node { int val; struct Node *left, *right; };
char* tokens[20]; int idx = 0;
struct Node* deserialize() {
char* token = tokens[idx++];
if (strcmp(token, "#") == 0) return NULL;
struct Node* n = malloc(sizeof(struct Node));
n->val = atoi(token); n->left = NULL; n->right = NULL;
n->left = deserialize();
n->right = deserialize();
return n;
}
int main() {
char data[] = "1 2 # # 3 # #";
char* tok = strtok(data, " ");
while (tok) { tokens[idx == 0 ? 0 : idx] = tok; tok = strtok(NULL, " "); }
idx = 0;
struct Node* root = deserialize();
printf("Rebuilt root value: %d\n", root->val);
return 0;
}Login to try C/C++/Java code in the editor
Round Trip
A correct serialize/deserialize implementation must be a perfect round trip: serializing a tree and then deserializing that output should reconstruct a tree that's structurally identical to the original, including the exact positions of any missing children.
Example: Round Trip
#include <iostream>
using namespace std;
int main() {
cout << "serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved");
}
}print("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved")#include <stdio.h>
int main() {
printf("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved\n");
return 0;
}Login to try C/C++/Java code in the editor
Practice
This pattern is essential anywhere tree-shaped data needs to leave memory and come back later — saving application state, transmitting tree structures across a network API, or persisting a parsed document structure to disk.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Used for saving app state, sending trees over a network, or persisting them to a file" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Used for saving app state, sending trees over a network, or persisting them to a file");
}
}print("Used for saving app state, sending trees over a network, or persisting them to a file")#include <stdio.h>
int main() {
printf("Used for saving app state, sending trees over a network, or persisting them to a file\n");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: