These are the notes for DSA episode 41. A tree lives in memory as objects joined by references; to save it in a file or send it over a network, it has to become one string, and the string has to turn back into exactly the same tree. We start from a real-life story (a family tree sent as a text message), define every word, try the first idea (preorder values only) and watch two different trees give the same string, add null markers, write the obvious code with String + and substring, watch it hit Time Limit Exceeded, and then solve it in O(n) with a StringBuilder, one split and an index that only moves forward. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
Your dadi has drawn the family tree on paper: each person, and below them at most two children, one on the left and one on the right. Your cousin abroad wants a copy, but you can only send a plain text message: letters, digits and commas, no photo. Your cousin redraws the tree from the message alone, and the drawing must be identical: the same people in the same places, and even the empty spots must match (if someone has a child only on the right, the copy must show that).
| With the family tree | In code |
|---|---|
| Writing the message | serialize: tree → string |
| Redrawing the tree from the message | deserialize: string → tree |
| One name or number in the message | a token |
| The commas between them | the delimiter |
| Writing "no child here" | a null marker, # |
| Checking the copy matches the original | the round trip |
Every word, from zero
- Binary tree, node, root, child, leaf,
null: from episode 36.nullmeans "no child here". - Preorder: visit the node, then its whole left subtree, then its whole right subtree (episode 36).
- Serialize: turn a data structure (here a tree) into one string, so it can be stored or sent.
- Deserialize: read that string and build the same structure back in memory.
- Token: one piece of the string, such as
12,-7or#. - Delimiter: the separator between tokens; we use a comma. Without it,
1then2and12look the same. - Null marker: a token that means "no node here"; we use
#. - Round trip: serialize, then deserialize, then compare: you must get the same values in the same shape.
- Immutable: cannot be changed after it is made. Java
Strings are immutable:s + tbuilds a new string. StringBuilder: a growable buffer of characters;appendadds to the end without copying what is already there.split(","): cuts a string at every comma and returns the pieces as aString[]. Trailing empty pieces are dropped, so"1,#,#,".split(",")has 3 tokens.Integer.parseInt(t): turns the text"-7"into theint−7; throwsNumberFormatExceptionfor text that is not a number, like"#".
Problem statement
Design two functions:
String serialize(Node root)turns a tree into a string;Node deserialize(String data)turns that string back into a tree.
The format is up to you; the only rule is deserialize(serialize(t)) must be the same tree as t.
| Input tree | Notes |
|---|---|
[1, 2, 3, null, null, 4, 5] |
root 1, left child 2, right child 3 with children 4 and 5 |
[] |
the empty tree: root == null |
[-7] |
negative values: the minus sign is part of a token |
Constraints: up to 10,000 nodes, values −1000 … 1000.
First idea: preorder values only
static String vals(Node n) {
if (n == null) return "";
return n.val + "," + vals(n.left) + vals(n.right);
}
Two different trees: x is a left chain (1 → left 2 → left 3) and y has root 1 with children 2 and 3.
Node x = new Node(1, new Node(2, new Node(3), null), null);
Node y = new Node(1, new Node(2), new Node(3));
System.out.println(vals(x));
System.out.println(vals(y));
Real output:
1,2,3,
1,2,3,
The same string for two different trees. The empty spots were thrown away, so the reader cannot tell whether 3 hangs under 2 or under 1. Fix: write a # for every empty child. Now x becomes 1,2,3,#,#,#,#, and y becomes 1,2,#,#,3,#,#,: different strings, and the #s tell the reader exactly where every subtree ends.
The obvious code: String + and substring
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static String slowSer(Node n) {
if (n == null) return "#,";
String s = "";
s = s + n.val + ",";
s = s + slowSer(n.left);
s = s + slowSer(n.right);
return s;
}
static Node slowDes(String[] rest) {
int c = rest[0].indexOf(',');
String tok = rest[0].substring(0, c);
rest[0] = rest[0].substring(c + 1);
if (tok.equals("#")) return null;
Node n = new Node(Integer.parseInt(tok));
n.left = slowDes(rest);
n.right = slowDes(rest);
return n;
}
public static void main(String[] args) {
Node x = new Node(1, new Node(2, new Node(3), null), null);
Node y = new Node(1, new Node(2), new Node(3));
Node a = new Node(1, new Node(2),
new Node(3, new Node(4), new Node(5)));
System.out.println(slowSer(x));
System.out.println(slowSer(y));
String s = slowSer(a);
System.out.println(s);
Node back = slowDes(new String[]{s});
System.out.println(slowSer(back).equals(s));
}
}
rest is a one-element array so that every recursive call shares (and shortens) the same unread text. Real output:
1,2,3,#,#,#,#,
1,2,#,#,3,#,#,
1,2,#,#,3,4,#,#,5,#,#,
true
Correct. Now a big tree: a complete tree 17 levels deep (131,071 nodes, random values −1000 … 1000):
static Random rnd = new Random(41);
static Node full(int d) {
if (d == 0) return null;
return new Node(rnd.nextInt(2001) - 1000, full(d - 1), full(d - 1));
}
// in main:
Node big = full(17);
long t0 = System.nanoTime();
String s = slowSer(big);
Node back = slowDes(new String[]{s});
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(s.length() + " chars, " + ms + " ms");
In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s). Without a limit it printed 837972 chars, 23721 ms.
Why it is slow
- Java
Strings are immutable:s + tcreates a brand-new string and copies both parts. InslowSer, the big strings from the children are copied again at every level on the way up. - In
slowDes, everysubstring(c + 1)copies the whole unread rest, once per token. - The big string has about 8.4 lakh characters and 2.6 lakh tokens (131,071 values + 131,072
#). 2.6 lakh copies of about 4 lakh characters each ≈ 10^11 character copies: O(n²).
The key insight: write once, read once
- Write into one
StringBuilderfor the whole tree.appendadds to the end; nothing already written is copied again. - Read by calling
split(",")once, then walking the tokens with one indexithat only moves forward. - The reader rebuilds in the same preorder the writer used: a node, then its whole left subtree, then its whole right subtree. The
#s tell it where each subtree ends.
Reading 1,2,#,#,3,4,#,#,5,#,#,:
| i | token | action |
|---|---|---|
| 0 | 1 |
root 1; build its left |
| 1 | 2 |
1.left = 2; build 2's left |
| 2 | # |
2.left = null |
| 3 | # |
2.right = null; back to 1 |
| 4 | 3 |
1.right = 3; build 3's left |
| 5 | 4 |
3.left = 4 |
| 6, 7 | #, # |
4 has no children |
| 8 | 5 |
3.right = 5 |
| 9, 10 | #, # |
5 has no children; every token used once |
Each token is written once and read once: O(n).
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static String serialize(Node root) {
StringBuilder sb = new StringBuilder();
write(root, sb);
return sb.toString();
}
static void write(Node n, StringBuilder sb) {
if (n == null) { sb.append("#,"); return; }
sb.append(n.val).append(',');
write(n.left, sb);
write(n.right, sb);
}
static String[] tok;
static int i;
static Node deserialize(String data) {
tok = data.split(",");
i = 0;
return read();
}
static Node read() {
String t = tok[i++];
if (t.equals("#")) return null;
Node n = new Node(Integer.parseInt(t));
n.left = read();
n.right = read();
return n;
}
static void check(Node t) {
String s = serialize(t);
String again = serialize(deserialize(s));
System.out.println(s + " same: " + s.equals(again));
}
public static void main(String[] args) {
Node a = new Node(1, new Node(2),
new Node(3, new Node(4), new Node(5)));
check(a);
check(null);
check(new Node(-7));
check(new Node(1000, null, new Node(-1000)));
}
}
Real output:
1,2,#,#,3,4,#,#,5,#,#, same: true
#, same: true
-7,#,#, same: true
1000,#,-1000,#,#, same: true
The empty tree is the single token #; the empty left spot of 1000 is kept.
The big tree in milliseconds
The same 131,071-node tree with serialize / deserialize: real output 837972 chars, 143 ms (the timing changes a little from run to run).
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};
void write(Node* n, string& out) {
if (!n) { out += "#,"; return; }
out += to_string(n->val);
out += ',';
write(n->left, out);
write(n->right, out);
}
string serialize(Node* root) { string out; write(root, out); return out; }
Node* readTok(const vector<string>& tok, size_t& i) {
const string& t = tok[i++];
if (t == "#") return nullptr;
Node* n = new Node(stoi(t));
n->left = readTok(tok, i);
n->right = readTok(tok, i);
return n;
}
Node* deserialize(const string& data) {
vector<string> tok;
string cur;
for (char c : data) {
if (c == ',') { tok.push_back(cur); cur.clear(); }
else cur += c;
}
size_t i = 0;
return readTok(tok, i);
}
void check(Node* t) {
string s = serialize(t);
cout << s << " same: " << boolalpha << (serialize(deserialize(s)) == s) << "\n";
}
int main() {
Node* a = new Node(1, new Node(2), new Node(3, new Node(4), new Node(5)));
check(a);
check(nullptr);
check(new Node(-7));
check(new Node(1000, nullptr, new Node(-1000)));
}
In C++, std::string is mutable, so out += appends in place (amortised O(1)); passing it by reference is what keeps this O(n). Real output (g++ -O2 -std=c++17): the same four lines, with same: true.
The same solution in Python
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def serialize(root):
out = []
def write(n):
if n is None:
out.append("#")
return
out.append(str(n.val))
write(n.left)
write(n.right)
write(root)
return ",".join(out) + ","
def deserialize(data):
tok = iter(data.split(",")[:-1])
def read():
t = next(tok)
if t == "#":
return None
n = Node(int(t))
n.left = read()
n.right = read()
return n
return read()
def check(t):
s = serialize(t)
print(s, " same:", serialize(deserialize(s)) == s)
a = Node(1, Node(2), Node(3, Node(4), Node(5)))
check(a)
check(None)
check(Node(-7))
check(Node(1000, None, Node(-1000)))
A list plus one ",".join plays the role of StringBuilder, and iter(...) with next is the index that only moves forward. Python's split keeps the trailing empty piece, so [:-1] drops it. Real output: the same four strings, with same: True.
Two real bugs
Bug 1: parsing before checking for #
static Node read() {
String t = tok[i++];
Node n = new Node(Integer.parseInt(t));
n.left = read();
n.right = read();
return n;
}
Real output:
Exception in thread "main" java.lang.NumberFormatException: For input string: "#"
at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:67)
at java.base/java.lang.Integer.parseInt(Integer.java:648)
...
# is not a number. Check t.equals("#") first.
Bug 2: the index is never reset
static int i = 0; // set once, when the class loads
static Node deserialize(String data) {
tok = data.split(","); // no "i = 0;" here
return read();
}
// main:
String s = serialize(a);
System.out.println(serialize(deserialize(s)));
System.out.println(serialize(deserialize(s)));
Real output:
1,2,#,#,3,4,#,#,5,#,#,
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 11 out of bounds for length 11
at Main.read(Main.java:28)
...
The first call left i at 11, the end of the tokens. Reset i = 0 inside deserialize, every call.
Also: very deep trees
Both write and read recurse once per level. On a chain tens of thousands of levels deep, Java throws java.lang.StackOverflowError (Python: RecursionError). Use level order (practice 1), which uses a queue instead of recursion.
Complexity
| Approach | Time | Space | Big tree (131,071 nodes) |
|---|---|---|---|
String + and substring |
O(n²) | O(n) string + O(h) recursion | 23.7 s → TLE |
StringBuilder + split once + moving index |
O(n) | O(n) string + O(h) recursion | 0.14 s |
n = number of nodes, h = height (about log n for a balanced tree, n for a chain).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Values only, no # |
1,2,3, for two different trees |
the empty spots are lost | write # for every null child |
| No delimiter | 1 then 2 reads like 12 |
tokens run together | a comma after every token |
Integer.parseInt(t) before the # check |
NumberFormatException: For input string: "#" |
# is not a number |
if (t.equals("#")) return null; first |
static int i = 0; only |
ArrayIndexOutOfBoundsException: Index 11 out of bounds for length 11 on the second call |
the index stays at the end | i = 0; inside deserialize |
s = s + ... and substring per token |
Time Limit Exceeded | the whole string copied again and again | StringBuilder, split once |
| Reading in a different order than writing | a different tree | preorder in, preorder out | same order both ways |
| Recursion on a very deep chain | StackOverflowError |
one stack frame per level | level order with a queue |
Mini project: the family-tree messenger
Make a Person node with a String name and left/right children. Serialize a small family tree (6–8 people) into one line, using # for empty spots and | as the delimiter (so names may contain commas). Print the message, deserialize it, and print the tree sideways (right subtree on top, indented by depth) to check it by eye. Then save the message to a file with Files.writeString and load it back.
Practice
- Serialize in level order (BFS), the way LeetCode prints trees.
Solution
Write: walk a growing list of nodes; each real node writes its value and adds both children (even null ones) to the list; a null writes #. Read: the first token is the root; a queue hands out parents, and each parent takes the next two tokens as its children.
static String levelSer(Node root) {
StringBuilder sb = new StringBuilder();
List<Node> order = new ArrayList<>();
order.add(root);
for (int j = 0; j < order.size(); j++) {
Node n = order.get(j);
if (n == null) { sb.append("#,"); continue; }
sb.append(n.val).append(',');
order.add(n.left);
order.add(n.right);
}
return sb.toString();
}
static Node levelDes(String data) {
String[] t = data.split(",");
if (t[0].equals("#")) return null;
Node root = new Node(Integer.parseInt(t[0]));
Deque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty()) {
Node n = q.poll();
if (!t[i].equals("#")) { n.left = new Node(Integer.parseInt(t[i])); q.add(n.left); }
i++;
if (!t[i].equals("#")) { n.right = new Node(Integer.parseInt(t[i])); q.add(n.right); }
i++;
}
return root;
}
Real output for example 1: 1,2,3,#,#,4,5,#,#,#,#, and the round trip is true. No recursion, so no stack overflow on deep trees.
- Serialize a BST with no
#at all (LeetCode 449). Why does it work?
Solution
In a binary search tree every value in the left subtree is smaller than the node and every value in the right subtree is bigger. So the preorder values alone are enough: while reading, a value belongs to the current spot only if it fits the allowed range [lo, hi].
static int[] v; static int k;
static Node bstRead(int lo, int hi) {
if (k == v.length || v[k] < lo || v[k] > hi) return null;
Node n = new Node(v[k++]);
n.left = bstRead(lo, n.val - 1);
n.right = bstRead(n.val + 1, hi);
return n;
}
For the BST 5 → (3 → 2, 4), (8 → right 9) the values are 5,3,2,4,8,9, and reading them back gives (printed with #s) 5,3,2,#,#,4,#,#,8,#,9,#,#,: the same tree. Real output.
- Read the tokens without
split, character by character.
Solution
static int p;
static Node charRead(String s) {
if (s.charAt(p) == '#') { p += 2; return null; } // skip "#,"
int sign = 1, x = 0;
if (s.charAt(p) == '-') { sign = -1; p++; }
while (s.charAt(p) != ',') x = x * 10 + (s.charAt(p++) - '0');
p++; // skip ','
Node n = new Node(sign * x);
n.left = charRead(s);
n.right = charRead(s);
return n;
}
With p = 0, charRead("-12,#,305,#,#,") rebuilds −12 with a right child 305 (printed back: -12,#,305,#,#,). Real output. This avoids creating a String for every token.
Quick quiz
Which tree does the string 5,#,8,#,#, build: 5 with a left child 8, 5 with a right child 8, 8 with a left child 5, or two separate nodes?
Answer
5 with a right child 8. 5 is the root; its left is the next token, # (no left child); its right is 8, which gets #, #.
Interview questions
- Why does preorder alone not work, but preorder with
#does? Without markers, the shape is lost (two trees, one string). With a marker for every null, the reader always knows where each subtree ends, so there is exactly one tree for each string. - Why do we need a delimiter? Values have different lengths and may be negative; without a separator
1,2and12are ambiguous. - Why is
s = s + tin a loop slow in Java? Strings are immutable; every+copies everything so far: O(n²) total.StringBuilder.appendis amortised O(1). - Preorder vs level order format? Both are O(n). Level order uses a queue (no deep recursion) and matches LeetCode's printing; preorder is shorter to code.
- How would you make the string smaller? Drop trailing
#s in level order, use a binary format (4 bytes per int), or, for a BST, skip#entirely (practice 2). - Time and space? O(n) time both ways; O(n) for the string, plus O(h) recursion.
- Where is serialization used for real? Saving to files, sending objects over a network (JSON, Protocol Buffers), caching, and copying data between programs.
Glossary
| Term | Meaning |
|---|---|
| Serialize | Turn a data structure into a string (or bytes) to store or send it |
| Deserialize | Build the same data structure back from that string |
| Token | One piece of the string, such as 12, -7 or # |
| Delimiter | The separator between tokens; here a comma |
| Null marker | A token meaning "no node here"; here # |
| Round trip | Serialize, deserialize, compare: the result must equal the original |
| Preorder | Node, then left subtree, then right subtree |
| Level order | Level by level, left to right, using a queue (BFS) |
| Immutable | Cannot change after creation; Java Strings are immutable |
StringBuilder |
A growable character buffer; append adds to the end without copying |
split(",") |
Cuts a string at every comma into a String[] |
Integer.parseInt |
Turns text like "-7" into an int |
NumberFormatException |
Thrown by parseInt for text that is not a number |
ArrayIndexOutOfBoundsException |
Thrown when an array index is below 0 or ≥ its length |
| Binary search tree (BST) | A binary tree where left values are smaller and right values bigger than the node |
| O(n), O(n²) | Running time growing linearly / with the square of the input size |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
StackOverflowError |
Java's error when recursion goes too deep for the call stack |
Summary
- Serialize = tree → string, deserialize = string → tree; the round trip must give the same tree.
- Values alone lose the shape: write
#for every null child and a comma after every token. String +andsubstringcopy the whole string again and again: O(n²), TLE on a big tree.- Write into one
StringBuilder; read with onesplitand an index that only moves forward, in the same preorder. O(n) time, O(n) space.
Next episode: Build a tree from preorder and inorder.