Serialize and Deserialize Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Serialization with Preorder Traversal

What is the output of the serialization function using preorder traversal on this binary tree?

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

DSA C

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

void serialize(Node* root, char* buffer) {
    if (root == NULL) {
        strcat(buffer, "#,");
        return;
    }
    char valStr[12];
    sprintf(valStr, "%d,", root->val);
    strcat(buffer, valStr);
    serialize(root->left, buffer);
    serialize(root->right, buffer);
}

// Assume buffer is large enough and initially empty

// Example usage:
// Node* root = ... (tree above)
// char buffer[100] = "";
// serialize(root, buffer);
// printf("%s", buffer);

A "1,2,3,4,5,#,#,#,#,#,#,"

B "1,3,5,#,#,4,#,#,2,#,#,"

C "1,2,#,#,3,4,#,#,5,#,#,"

D "#,1,2,#,#,3,4,#,#,5,#,#"

💡 Hint

Think about preorder traversal: root, left subtree, then right subtree. Use '#' to mark null nodes.

The serialization uses preorder traversal. It visits root (1), then left subtree (2), which has no children (#,#), then right subtree (3), then its left child (4) with no children (#,#), then right child (5) with no children (#,#). So the output is "1,2,#,#,3,4,#,#,5,#,#,".

❓ Predict Output

intermediate

Resulting Tree After Deserialization

Given the serialized string "1,2,#,#,3,4,#,#,5,#,#," what is the structure of the binary tree after deserialization?

DSA C

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

// Deserialization function reads values from the string and reconstructs the tree
// '#' means NULL node

// After deserialization, print the tree in inorder traversal (left, root, right)
// Expected output format: "2 -> 1 -> 4 -> 3 -> 5 -> null"

A "2 -> 1 -> 4 -> 3 -> 5 -> null"

B "1 -> 2 -> 3 -> 4 -> 5 -> null"

C "5 -> 4 -> 3 -> 2 -> 1 -> null"

D "null"

💡 Hint

Remember inorder traversal visits left child, then root, then right child.

The deserialized tree matches the original tree. Inorder traversal visits nodes in order: left subtree (2), root (1), left child of right subtree (4), right subtree root (3), right child of right subtree (5). So the output is "2 -> 1 -> 4 -> 3 -> 5 -> null".

🔧 Debug

advanced

Identify the Bug in Serialization Code

What error will this serialization code cause when run on a binary tree?

DSA C

void serialize(Node* root, char* buffer) {
    if (root == NULL) {
        strcat(buffer, "#"); // Missing comma here
        return;
    }
    char valStr[12];
    sprintf(valStr, "%d,", root->val);
    strcat(buffer, valStr);
    serialize(root->left, buffer);
    serialize(root->right, buffer);
}

A The code will not compile due to missing semicolon.

B The output string will have missing commas between null markers, causing incorrect deserialization.

C The code will cause a segmentation fault due to buffer overflow.

D The code will produce an empty string.

💡 Hint

Check how null nodes are marked in the output string.

The null nodes are marked with "#" but without a comma after it. This causes the serialized string to have missing commas between null markers, which breaks the format expected by deserialization.

❓ Predict Output

advanced

Output of Deserialization with Incorrect Input

What error or output results from deserializing the string "1,2,#,3,#,#,#,"?

DSA C

// Deserialization reads values separated by commas
// '#' means NULL node
// The string is malformed because it misses some null markers

// The deserialization function expects a complete preorder serialization
// What happens when it tries to build the tree?

A Tree is built successfully with root 1, left child 2, and left child of 2 is 3.

B The deserialization produces a tree with root 1 and no children.

C The function returns NULL because input is invalid.

D Runtime error due to unexpected end of input during deserialization.

💡 Hint

Check if the input string has enough markers for all nodes and null children.

The input string is incomplete and does not provide enough null markers for all children. The deserialization function will try to read beyond the string and cause a runtime error (e.g., reading invalid memory or crashing).

🧠 Conceptual

expert

Why Use '#' in Serialization of Binary Trees?

Why is it necessary to include a special marker like '#' for null nodes when serializing a binary tree?

A To uniquely represent the tree structure including missing children, enabling correct deserialization.

B To reduce the size of the serialized string by skipping null nodes.

C To mark the end of the serialized string for parsing convenience.

D To indicate leaf nodes that have no children.

💡 Hint

Think about how the deserialization function knows where left and right children are missing.

Including '#' for null nodes ensures the serialized string captures the exact shape of the tree, including where children are missing. Without it, deserialization cannot reconstruct the original tree uniquely.

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