SyntaxPilot
Courses/DSA and Coding Problems/Lesson 41
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 41 of 90

Serialize and deserialize a binary tree (hard)

queued

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. null means "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, -7 or #.
  • Delimiter: the separator between tokens; we use a comma. Without it, 1 then 2 and 12 look 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 + t builds a new string.
  • StringBuilder: a growable buffer of characters; append adds to the end without copying what is already there.
  • split(","): cuts a string at every comma and returns the pieces as a String[]. Trailing empty pieces are dropped, so "1,#,#,".split(",") has 3 tokens.
  • Integer.parseInt(t): turns the text "-7" into the int −7; throws NumberFormatException for 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 + t creates a brand-new string and copies both parts. In slowSer, the big strings from the children are copied again at every level on the way up.
  • In slowDes, every substring(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

  1. Write into one StringBuilder for the whole tree. append adds to the end; nothing already written is copied again.
  2. Read by calling split(",") once, then walking the tokens with one index i that only moves forward.
  3. 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

  1. 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.

  1. 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.

  1. 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

  1. 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.
  2. Why do we need a delimiter? Values have different lengths and may be negative; without a separator 1, 2 and 12 are ambiguous.
  3. Why is s = s + t in a loop slow in Java? Strings are immutable; every + copies everything so far: O(n²) total. StringBuilder.append is amortised O(1).
  4. 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.
  5. 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).
  6. Time and space? O(n) time both ways; O(n) for the string, plus O(h) recursion.
  7. 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 + and substring copy the whole string again and again: O(n²), TLE on a big tree.
  • Write into one StringBuilder; read with one split and 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.