Serialize and Deserialize Binary Tree in DSA C++

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact same tree from that string.

Analogy: Like writing a family tree on paper with names and empty spots, then reading it back to draw the same tree again.

    1
   / \
  2   3
     / \
    4   5

Serialized as: "1,2,null,null,3,4,null,null,5,null,null"

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree to a string and then rebuild the exact same tree from that string

Step 1: Start serialization at root node 1

Serialized string: "1,"

Why: We record the root value first to know where the tree starts

Step 2: Serialize left subtree of 1 (node 2)

Serialized string: "1,2,"

Why: We record left child to keep tree structure

Step 3: Serialize left child of 2 which is null

Serialized string: "1,2,null,"

Why: Null marks where branches end

Step 4: Serialize right child of 2 which is null

Serialized string: "1,2,null,null,"

Why: Both children null means leaf node

Step 5: Serialize right subtree of 1 (node 3)

Serialized string: "1,2,null,null,3,"

Why: Continue with right child to keep full tree

Step 6: Serialize left child of 3 (node 4)

Serialized string: "1,2,null,null,3,4,"

Why: Record left child of 3

Step 7: Serialize left and right children of 4 which are null

Serialized string: "1,2,null,null,3,4,null,null,"

Why: Leaf node 4 ends here

Step 8: Serialize right child of 3 (node 5) and its null children

Serialized string: "1,2,null,null,3,4,null,null,5,null,null,"

Why: Finish right subtree serialization

Step 9: Start deserialization from string

Reading "1" creates root node 1

Why: Rebuild root first

Step 10: Deserialize left subtree from next tokens "2,null,null"

Node 2 created with null children

Why: Rebuild left subtree exactly

Step 11: Deserialize right subtree from remaining tokens "3,4,null,null,5,null,null"

Node 3 with children 4 and 5 rebuilt

Why: Rebuild right subtree exactly

Result:

Tree rebuilt exactly as:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA C++

#include <iostream>
#include <string>
#include <sstream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    // Serialize tree to string using preorder traversal
    string serialize(TreeNode* root) {
        if (!root) return "null,"; // mark null nodes
        return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
    }

    // Helper to deserialize from stream
    TreeNode* deserializeHelper(queue<string>& nodes) {
        string val = nodes.front();
        nodes.pop();
        if (val == "null") return nullptr; // null node
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserializeHelper(nodes); // build left subtree
        node->right = deserializeHelper(nodes); // build right subtree
        return node;
    }

    // Deserialize string to tree
    TreeNode* deserialize(string data) {
        queue<string> nodes;
        string token;
        stringstream ss(data);
        while (getline(ss, token, ',')) {
            if (!token.empty()) {
                nodes.push(token);
            }
        }
        return deserializeHelper(nodes);
    }
};

// Helper to print tree inorder for verification
void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}

int main() {
    // Build tree: 1
    //            /   \
    //           2     3
    //                / \
    //               4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    Codec codec;
    string serialized = codec.serialize(root);
    cout << "Serialized: " << serialized << endl;

    TreeNode* deserializedRoot = codec.deserialize(serialized);
    cout << "Inorder of deserialized tree: ";
    printInorder(deserializedRoot);
    cout << endl;

    return 0;
}

if (!root) return "null,";

mark null nodes to preserve tree shape

return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);

serialize current node then left and right subtrees

string val = nodes.front(); nodes.pop();

read next token from serialized data

if (val == "null") return nullptr;

null token means no node here

TreeNode* node = new TreeNode(stoi(val));

create node with current value

node->left = deserializeHelper(nodes);

rebuild left subtree recursively

node->right = deserializeHelper(nodes);

rebuild right subtree recursively

Output

Serialized: 1,2,null,null,3,4,null,null,5,null,null,

Inorder of deserialized tree: 2 1 4 3 5 

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) for the output string and the recursion stack in worst case

vs Alternative: Compared to level order serialization, preorder with null markers is simpler and handles any tree shape without extra data

Edge Cases

Empty tree (root is null)

Serialize returns "null," and deserialize returns nullptr

DSA C++

if (!root) return "null,";

Tree with only one node

Serialize outputs value with two null children markers; deserialize rebuilds single node

DSA C++

if (val == "null") return nullptr;

Tree with only left or only right children

Null markers correctly preserve missing branches during serialization and deserialization

DSA C++

return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);

When to Use This Pattern

When you need to save or send a tree and then rebuild it exactly, use serialize/deserialize with preorder and null markers to keep structure intact.

Common Mistakes

Mistake: Not marking null children during serialization, causing loss of tree shape
Fix: Add explicit "null" markers for missing children to preserve structure

Mistake: Using inorder traversal for serialization which cannot uniquely rebuild the tree
Fix: Use preorder or postorder with null markers to keep unique structure

Summary

It converts a binary tree into a string and back to the exact same tree.

Use it when you want to save or transfer a tree and restore it later.

The key is to record null children explicitly to keep the tree shape.