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

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you have a family tree stored as a binary tree in your computer. You want to save this tree to a file so you can share it or load it later. To do this, you need to convert the tree into a string (serialize) and then convert the string back into the tree (deserialize).

🎯 Goal: You will build a program that can convert a binary tree into a string and then rebuild the same tree from that string. This helps in saving and loading tree data easily.

📋 What You'll Learn

Create a binary tree node structure with integer values.

Write a function to serialize the binary tree into a string using preorder traversal.

Write a function to deserialize the string back into the original binary tree.

Use a special marker (e.g., '#') to represent NULL nodes in the serialization.

Print the serialized string and verify the deserialized tree by printing its preorder traversal.

💡 Why This Matters

🌍 Real World

Saving and loading tree data structures is common in databases, file systems, and network communication where data needs to be stored or sent efficiently.

💼 Career

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

1

Create the Binary Tree Structure and Sample Tree

Create a struct called Node with an int data and two pointers left and right. Then create a sample binary tree with root node value 1, left child 2, and right child 3. The left child of node 3 should be 4 and right child 5.

DSA C

# Define struct Node and create the sample tree
// Your code here

Hint

Use a struct with pointers for left and right children. Use a helper function to create nodes.

2

Add a Buffer String and Index for Serialization

Create a character array called buffer of size 100 to hold the serialized string. Also create an integer variable index initialized to 0 to track the position in the buffer.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->right->left = createNode(4);
    root->right->right = createNode(5);

    char buffer[100];
    int index = 0;
    // Your code here

    return 0;
}

Hint

Use a char array to store the serialized string and an int to track the current position.

3

Write the Serialize Function Using Preorder Traversal

Write a function called serialize that takes a Node* called root, the buffer array, and a pointer to index. It should add the node's data to buffer as a string followed by a space. If the node is NULL, add # to buffer. Use preorder traversal (root, left, right) to serialize the entire tree.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void serialize(Node* root, char* buffer, int* index) {
    // Add serialization code here
    // Your code here
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->right->left = createNode(4);
    root->right->right = createNode(5);

    char buffer[100];
    int index = 0;

    serialize(root, buffer, &index);
    buffer[index] = '\0';

    return 0;
}

Hint

Use recursion. For NULL nodes, add '# '. For non-NULL, add the number and a space, then recurse left and right.

4

Write the Deserialize Function and Print Serialized String

Write a function called deserialize that takes the buffer string and a pointer to an integer pos to track the current position. It should read the next token from buffer. If the token is #, return NULL. Otherwise, create a new node with the integer value and recursively build its left and right children. In main, call deserialize with buffer and pos = 0 to rebuild the tree. Then print the serialized string using printf.

DSA C

#include 
#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void serialize(Node* root, char* buffer, int* index) {
    if (root == NULL) {
        buffer[(*index)++] = '#';
        buffer[(*index)++] = ' ';
        return;
    }
    int n = sprintf(buffer + *index, "%d ", root->data);
    *index += n;
    serialize(root->left, buffer, index);
    serialize(root->right, buffer, index);
}

Node* deserialize(char* buffer, int* pos) {
    // Add deserialization code here
    // Your code here
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->right->left = createNode(4);
    root->right->right = createNode(5);

    char buffer[100];
    int index = 0;

    serialize(root, buffer, &index);
    buffer[index] = '\0';

    int pos = 0;
    Node* newRoot = deserialize(buffer, &pos);

    printf("%s\n", buffer);

    return 0;
}

Hint

Read tokens from the buffer. If token is '#', return NULL. Otherwise, create node and recursively build left and right. Use pos to track position.

Practice

1. What is the main purpose of serialize and deserialize functions in the context of a binary tree?

easy

A. Delete all nodes in the binary tree

B. Sort the binary tree nodes in ascending order

C. Find the height of the binary tree

D. Convert a binary tree to a string and back to a binary tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a binary tree into a string format so it can be stored or sent easily.

2. Step 2: Understand deserialization

   Deserialization means converting the string back into the original binary tree structure.

3. Final Answer:

   Convert a binary tree to a string and back to a binary tree -> Option D

4. Quick Check:

   Serialize + Deserialize = Convert tree to string and back [OK]

Hint: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Thinking serialization sorts nodes
• Confusing serialization with deletion
• Believing serialization finds tree height

2. Which of the following is the correct way to represent a null node during serialization of a binary tree in C?

easy

A. "null"

B. "#"

C. "0"

D. "-1"

Solution

1. Step 1: Identify common null markers

   In many serialization methods, a special symbol like "#" is used to mark null nodes to distinguish them from valid values.

2. Step 2: Compare options

   "null" is a string but longer; "0" and "-1" can be valid node values, so "#" is safest and most common.

3. Final Answer:

   "#" -> Option B

4. Quick Check:

   Null node marker = "#" [OK]

Hint: Use '#' to mark null nodes in serialization [OK]

Common Mistakes:

• Using '0' which can be a valid node value
• Using 'null' string which is verbose
• Using '-1' which might be a valid value

3. Given the following serialized string of a binary tree using preorder traversal: "1,2,#,#,3,4,#,#,5,#,#", what is the inorder traversal of the tree?

medium

A. 1 2 3 4 5

B. 2 4 1 3 5

C. 2 1 4 3 5

D. 4 2 5 3 1

Solution

1. Step 1: Reconstruct the tree from preorder

   Preorder: root, left, right. The string means:
   Root=1
   Left subtree: 2, #, # (2 with no children)
   Right subtree: 3,4,#,#,5,#,# (3 with left=4 no children, right=5 no children)

2. Step 2: Find inorder traversal

   Inorder: left, root, right
   Left subtree inorder: 2
   Root: 1
   Right subtree inorder: left(4), root(3), right(5) -> 4 3 5
   Combine: 2 1 4 3 5

3. Final Answer:

   2 1 4 3 5 -> Option C

4. Quick Check:

   Preorder to inorder conversion = 2 1 4 3 5 [OK]

Hint: Rebuild tree from preorder, then do inorder traversal [OK]

Common Mistakes:

• Mixing preorder and inorder orders
• Ignoring null markers and misbuilding tree
• Swapping left and right children

4. Consider this buggy C code snippet for deserializing a binary tree node from a string token:

if (strcmp(token, "#") == 0) {
    return NULL;
}
node = malloc(sizeof(TreeNode));
node->val = atoi(token);
node->left = deserialize(tokens);
node->right = deserialize(tokens);
return node;

What is the main issue causing incorrect deserialization?

medium

A. Not advancing the token pointer before recursive calls

B. Using atoi instead of strtol for conversion

C. Not checking if malloc returns NULL

D. Comparing token with "#" incorrectly

Solution

1. Step 1: Understand token usage

   Deserialization uses tokens from a list or array. Each recursive call must move to the next token to read the next node.

2. Step 2: Identify missing token advancement

   The code does not advance the token pointer before calling deserialize recursively, so it reads the same token repeatedly causing infinite recursion or wrong tree.

3. Final Answer:

   Not advancing the token pointer before recursive calls -> Option A

4. Quick Check:

   Advance token pointer before recursion [OK]

Hint: Always move to next token before recursive deserialize calls [OK]

Common Mistakes:

• Ignoring token pointer movement
• Focusing on atoi vs strtol which is less critical here
• Missing malloc NULL check but not main bug

5. You want to serialize a binary tree and then deserialize it back. Which approach ensures the tree structure is preserved even if node values contain commas or special characters?

hard

A. Use level-order traversal with a delimiter and escape special characters in node values

B. Use preorder traversal with commas and '#' for nulls without escaping

C. Serialize only node values ignoring nulls

D. Store tree as an array without any delimiter

Solution

1. Step 1: Understand problem with special characters

   If node values contain commas or special symbols, simple comma separation breaks parsing because commas appear inside values.

2. Step 2: Use level-order with escaping

   Level-order traversal with a delimiter and escaping special characters ensures each node value is correctly separated and nulls are marked, preserving structure.

3. Step 3: Why other options fail

   Use preorder traversal with commas and '#' for nulls without escaping fails because no escaping means parsing errors. Serialize only node values ignoring nulls loses structure by ignoring nulls. Store tree as an array without any delimiter without delimiter cannot separate nodes.

4. Final Answer:

   Use level-order traversal with a delimiter and escape special characters in node values -> Option A

5. Quick Check:

   Escape special chars + delimiter + level-order = safe serialization [OK]

Hint: Escape special chars and use delimiter in level-order serialization [OK]

Common Mistakes:

• Ignoring special characters in node values
• Not escaping delimiters causing parse errors
• Skipping null nodes losing tree shape