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 tree from that string exactly as it was.

Analogy: Like writing a family tree on paper with names and empty spots, then reading it back to draw the same family 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: Serialize root node 1

Serialized string: "1,"

Why: Start with root value to record the tree

Step 2: Serialize left child 2

Serialized string: "1,2,"

Why: Record left subtree starting with node 2

Step 3: Serialize left child of 2 which is null

Serialized string: "1,2,null,"

Why: Mark null to keep tree shape

Step 4: Serialize right child of 2 which is null

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

Why: Mark null to keep tree shape

Step 5: Serialize right child 3

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

Why: Record right subtree starting with node 3

Step 6: Serialize left child 4 of 3

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

Why: Record left subtree of node 3

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

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

Why: Mark nulls to keep tree shape

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

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

Why: Complete serialization of right subtree

Step 9: Deserialize string back to tree starting from first value

Tree rebuilt with root 1, left 2, right 3, and children 4 and 5

Why: Use string tokens to rebuild tree structure exactly

Result:

Tree structure:
    1
   / \
  2   3
     / \
    4   5

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define tree node
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Create new node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Serialize helper: write preorder traversal to string
void serializeHelper(TreeNode* root, char* str) {
    if (root == NULL) {
        strcat(str, "null,"); // mark null
        return;
    }
    char buffer[12];
    sprintf(buffer, "%d,", root->val);
    strcat(str, buffer); // add node value
    serializeHelper(root->left, str); // serialize left subtree
    serializeHelper(root->right, str); // serialize right subtree
}

// Serialize tree to string
char* serialize(TreeNode* root) {
    char* str = (char*)malloc(1000 * sizeof(char));
    str[0] = '\0';
    serializeHelper(root, str);
    return str;
}

// Helper to read next token from string
char* nextToken(char** strPtr) {
    char* str = *strPtr;
    if (*str == '\0') return NULL;
    char* token = str;
    while (*str != ',' && *str != '\0') str++;
    if (*str == ',') {
        *str = '\0';
        *strPtr = str + 1;
    } else {
        *strPtr = str;
    }
    return token;
}

// Deserialize helper: build tree from tokens
TreeNode* deserializeHelper(char** strPtr) {
    char* token = nextToken(strPtr);
    if (token == NULL || strcmp(token, "null") == 0) {
        return NULL; // null node
    }
    int val = atoi(token);
    TreeNode* root = newNode(val);
    root->left = deserializeHelper(strPtr); // build left subtree
    root->right = deserializeHelper(strPtr); // build right subtree
    return root;
}

// Deserialize string to tree
TreeNode* deserialize(char* data) {
    return deserializeHelper(&data);
}

// Print tree inorder for verification
void printInorder(TreeNode* root) {
    if (root == NULL) return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

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

    // Serialize
    char* serialized = serialize(root);
    printf("Serialized: %s\n", serialized);

    // Deserialize
    TreeNode* newRoot = deserialize(serialized);

    // Print inorder of deserialized tree
    printf("Inorder of deserialized tree: ");
    printInorder(newRoot);
    printf("\n");

    free(serialized);
    return 0;
}

if (root == NULL) { strcat(str, "null,"); return; }

mark null nodes to preserve tree shape during serialization

sprintf(buffer, "%d,", root->val); strcat(str, buffer);

append current node value to serialized string

serializeHelper(root->left, str);

serialize left subtree recursively

serializeHelper(root->right, str);

serialize right subtree recursively

char* token = nextToken(strPtr); if (token == NULL || strcmp(token, "null") == 0) return NULL;

read next token and return NULL if it marks a null node

int val = atoi(token); TreeNode* root = newNode(val);

create new node with current token value

root->left = deserializeHelper(strPtr);

build left subtree recursively

root->right = deserializeHelper(strPtr);

build 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 string storing all node values and recursion stack in worst case

vs Alternative: Compared to level-order serialization, preorder with null markers is simpler and uses recursion, but both have similar O(n) cost

Edge Cases

Empty tree (root is NULL)

Serialization returns "null," and deserialization returns NULL tree

DSA C

if (root == NULL) { strcat(str, "null,"); return; }

Tree with single node

Serialization returns "val,null,null," and deserialization rebuilds single node tree

DSA C

if (root == NULL) { strcat(str, "null,"); return; }

Tree with only left or only right children

Null markers preserve missing children so tree shape is maintained

DSA C

if (token == NULL || strcmp(token, "null") == 0) return NULL;

When to Use This Pattern

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

Common Mistakes

Mistake: Not marking null children during serialization, causing incorrect tree shape on deserialization
Fix: Always add a special marker like "null" for missing children

Mistake: Not advancing the string pointer correctly during deserialization, causing infinite loops or wrong nodes
Fix: Use a pointer reference and update it after reading each token

Summary

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

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

The key is to record null children so the tree shape is not lost.

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