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++

#include <bits/stdc++.h>

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

void serialize(TreeNode* root, std::string& out) {
    if (!root) {
        out += "#,";
        return;
    }
    out += std::to_string(root->val) + ",";
    serialize(root->left, out);
    serialize(root->right, out);
}

int main() {
    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);
    std::string result;
    serialize(root, result);
    std::cout << result << std::endl;
    return 0;
}

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

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

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

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

💡 Hint

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

The serialization uses preorder traversal. For each node, we add its value followed by a comma. For null children, we add '#,'. The output matches preorder: 1, then left subtree (2,#,#), then right subtree (3,4,#,#,5,#,#).

❓ Predict Output

intermediate

Result of Deserializing a Serialized String

Given the serialized string "1,2,#,#,3,4,#,#,5,#,#," representing a binary tree, what is the value of the root's right child's left child after deserialization?

DSA C++

#include <bits/stdc++.h>

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

TreeNode* deserialize(std::istringstream& in) {
    std::string val;
    if (!getline(in, val, ',')) return nullptr;
    if (val == "#") return nullptr;
    TreeNode* node = new TreeNode(std::stoi(val));
    node->left = deserialize(in);
    node->right = deserialize(in);
    return node;
}

int main() {
    std::string data = "1,2,#,#,3,4,#,#,5,#,#,";
    std::istringstream in(data);
    TreeNode* root = deserialize(in);
    std::cout << root->right->left->val << std::endl;
    return 0;
}

A 2

B 5

C 3

D 4

💡 Hint

Follow the preorder deserialization: root, left subtree, right subtree. The right child's left child is the node after 3 in preorder.

The deserialization reconstructs the tree from preorder. The root is 1, its right child is 3, and 3's left child is 4.

🧠 Conceptual

advanced

Why Use '#' in Serialization?

Why do we use the special marker '#' in the serialized string of a binary tree?

A To separate node values in the string

B To represent null (empty) children in the tree

C To mark the end of the serialized string

D To indicate the root node of the tree

💡 Hint

Think about how to represent missing children in a binary tree serialization.

The '#' symbol is used to represent null children so that the structure of the tree can be fully reconstructed during deserialization.

❓ Predict Output

advanced

Output of Deserialization with Incorrect Input

What error or output occurs when deserializing the string "1,2,#,3,#,#,#," using the given deserialize function?

DSA C++

#include <bits/stdc++.h>

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

TreeNode* deserialize(std::istringstream& in) {
    std::string val;
    if (!getline(in, val, ',')) return nullptr;
    if (val == "#") return nullptr;
    TreeNode* node = new TreeNode(std::stoi(val));
    node->left = deserialize(in);
    node->right = deserialize(in);
    return node;
}

int main() {
    std::string data = "1,2,#,3,#,#,#,";
    std::istringstream in(data);
    TreeNode* root = deserialize(in);
    std::cout << root->left->left->val << std::endl;
    return 0;
}

A Compilation error

B 3

C Segmentation fault (runtime error)

D 0

💡 Hint

Check if the input string matches the expected preorder serialization format with null markers.

The input string is malformed and does not represent a valid preorder serialization. The deserialize function will create a node where it expects a null, leading to a missing node and a runtime error when accessing root->left->left->val.

🚀 Application

expert

Number of Nodes After Deserialization

After deserializing the string "10,5,#,#,15,12,#,#,20,#,#," into a binary tree, how many nodes does the tree contain?

DSA C++

#include <bits/stdc++.h>

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

TreeNode* deserialize(std::istringstream& in) {
    std::string val;
    if (!getline(in, val, ',')) return nullptr;
    if (val == "#") return nullptr;
    TreeNode* node = new TreeNode(std::stoi(val));
    node->left = deserialize(in);
    node->right = deserialize(in);
    return node;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    std::string data = "10,5,#,#,15,12,#,#,20,#,#,";
    std::istringstream in(data);
    TreeNode* root = deserialize(in);
    std::cout << countNodes(root) << std::endl;
    return 0;
}

A 5

B 6

C 4

D 7

💡 Hint

Count all nodes including root and all children reconstructed from the serialized string.

The tree nodes are 10 (root), 5 (left child), 15 (right child), 12 (left child of 15), and 20 (right child of 15). Total nodes = 5.

Practice

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

easy

A. Find the height of the binary tree

B. Sort the binary tree nodes in ascending order

C. Delete all nodes 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 data structure like a binary tree into a string format that can be stored or transmitted.

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/from string [OK]

Hint: Think of serialize as packing, deserialize as unpacking [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking it deletes nodes
• Assuming it calculates tree height

2. Which of the following is a correct way to represent a null node during serialization of a binary tree in C++ using a single-character marker?

easy

A. "null"

B. "#"

C. 0

D. -1

Solution

1. Step 1: Identify common null markers

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

2. Step 2: Compare options

   "null" is a string but longer and less common; 0 and -1 can be valid node values, so they are ambiguous.

3. Final Answer:

   "#" -> Option B

4. Quick Check:

   Null node marker = "#" [OK]

Hint: Use a unique symbol like '#' for null nodes [OK]

Common Mistakes:

• Using 0 or -1 which can be valid node values
• Using the word "null" which is verbose
• Not marking null nodes at all

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

medium

A. 2 1 4 3 5

B. 1 2 3 4 5

C. 2 4 1 5 3

D. 3 2 1 5 4

Solution

1. Step 1: Reconstruct the tree from preorder

   Preorder: 1 (root), 2 (left child), # (left null), # (right null), 3 (right child), 4 (left child), #, #, 5 (right child), #, #.

2. Step 2: Draw the tree and find inorder

   Tree structure:
       1
     /     \
    2        3
             /  \
           4      5
   Inorder (left, root, right): 2 1 4 3 5

3. Final Answer:

   2 1 4 3 5 -> Option A

4. Quick Check:

   Inorder from tree = 2 1 4 3 5 [OK]

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

Common Mistakes:

• Mixing preorder and inorder sequences
• Ignoring null markers
• Incorrect tree reconstruction

4. Consider this C++ snippet for deserializing a binary tree from a vector of strings representing preorder traversal with '#' as null marker:

TreeNode* deserializeHelper(vector<string>& data, int& index) {
  if (index >= data.size() || data[index] == "#") {
    index++;
    return nullptr;
  }
  TreeNode* node = new TreeNode(stoi(data[index++]));
  node->left = deserializeHelper(data, index);
  node->right = deserializeHelper(data, index);
  return node;
}

What is the bug in this code?

medium

A. The stoi conversion can throw exception without try-catch

B. The index is incremented twice for null nodes causing skipping elements

C. The function does not handle empty input vector

D. The function does not assign right child correctly

Solution

1. Step 1: Identify the stoi vulnerability

   The code uses stoi(data[index++]) without validating that data[index] is a valid integer string. Malformed input (non-numeric other than '#') causes unhandled std::invalid_argument exception.

2. Step 2: Rule out other options

   Index increments once per token: for '#' via index++ in if; for values via index++ in stoi. Empty input handled by index >= data.size(). Right child assigned correctly.

3. Final Answer:

   The stoi conversion can throw exception without try-catch -> Option A

4. Quick Check:

   stoi requires valid numeric strings [OK]

Hint: Validate inputs before stoi to prevent exceptions [OK]

Common Mistakes:

• Assuming no index increment for null nodes
• Ignoring possible exceptions from stoi
• Thinking right child assignment is missing

5. You want to serialize a binary tree and then deserialize it back. However, your tree contains integer node values that can be negative, zero, or positive. Which approach ensures correct serialization and deserialization without ambiguity?

hard

A. Serialize only node values ignoring nulls, reconstruct tree by sorting

B. Use comma-separated values but skip null markers to reduce size

C. Use space-separated values with '#' for nulls and convert strings to int using stoi

D. Serialize using preorder but replace negative values with zero

Solution

1. Step 1: Consider node values including negatives and zero

   Using space-separated values with '#' for nulls preserves structure and allows negative values as strings can represent negatives.

2. Step 2: Evaluate other options

   Use comma-separated values but skip null markers to reduce size skips nulls, losing tree shape.
   Serialize only node values ignoring nulls, reconstruct tree by sorting ignores nulls and sorts, losing original structure.
   Serialize using preorder but replace negative values with zero replaces negatives with zero, losing data.

3. Final Answer:

   Use space-separated values with '#' for nulls and convert strings to int using stoi -> Option C

4. Quick Check:

   Preserve nulls and convert strings properly [OK]

Hint: Keep null markers and convert strings carefully [OK]

Common Mistakes:

• Skipping null markers losing tree shape
• Replacing negative values losing data
• Sorting nodes losing original tree