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.