Serialize and Deserialize Binary Tree in DSA C++ - Build from Scratch

Serialize and Deserialize Binary Tree

📖 Scenario: You are working on a system that needs to save and load binary trees efficiently. To do this, you will convert the tree into a string format (serialize) and then rebuild the tree from that string (deserialize).

🎯 Goal: Build two functions: one to serialize a binary tree into a string, and another to deserialize that string back into the original binary tree structure.

📋 What You'll Learn

Create a binary tree node structure with integer values

Write a serialize function that converts the tree into a string using preorder traversal

Write a deserialize function that rebuilds the tree from the serialized string

Use "#" to represent null nodes and commas "," to separate values

Print the serialized string and the inorder traversal of the deserialized tree

💡 Why This Matters

🌍 Real World

Saving and loading tree structures in databases, file systems, or network transmission often requires serialization and deserialization.

💼 Career

Understanding serialization is important for software engineers working with data storage, distributed systems, and APIs that exchange complex data.

1

Create the Binary Tree Node Structure and Sample Tree

Create a struct called TreeNode with an int val, and two pointers left and right. Then create a sample binary tree with root value 1, left child 2, and right child 3. The right child 3 should have two children: left 4 and right 5.

DSA C++

// Define TreeNode struct and create the sample tree
// Your code here

Hint

Define the struct with a constructor. Then create nodes and link them as described.

2

Add a Helper Function to Append Values to String

Create a helper function called void serializeHelper(TreeNode* node, std::string& str) that appends the node's value to str followed by a comma. If the node is nullptr, append "#," instead. Use preorder traversal (node, left, right).

DSA C++

void serializeHelper(TreeNode* node, std::string& str) {
    // Your code here
}

Hint

Use preorder traversal: process current node, then left subtree, then right subtree. Use # for null nodes.

3

Implement the Deserialize Helper Function

Create a function TreeNode* deserializeHelper(std::istringstream& ss) that reads values separated by commas from ss. If the value is "#", return nullptr. Otherwise, create a new TreeNode with the integer value, then recursively build its left and right children by calling deserializeHelper.

DSA C++

TreeNode* deserializeHelper(std::istringstream& ss) {
    // Your code here
}

Hint

Read each value from the string stream. Use recursion to rebuild left and right subtrees.

4

Serialize the Tree, Deserialize it, and Print Inorder Traversal

Create a function std::string serialize(TreeNode* root) that returns the serialized string by calling serializeHelper. Then create a function TreeNode* deserialize(const std::string& data) that uses deserializeHelper with a std::istringstream. Finally, write a function void inorder(TreeNode* root) that prints the tree values in inorder traversal separated by spaces. Call serialize on root, print the serialized string, then call deserialize on that string, and print the inorder traversal of the deserialized tree.

DSA C++

std::string serialize(TreeNode* root) {
    // Your code here
}

TreeNode* deserialize(const std::string& data) {
    // Your code here
}

void inorder(TreeNode* root) {
    // Your code here
}

int main() {
    // Your code here
    return 0;
}

Hint

Use the helper functions to build serialize and deserialize. Then print the serialized string and the inorder traversal of the deserialized tree.