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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the serialized tree?

Given the following binary tree and serialization method, what is the serialized string output?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Codec {
    public string serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }
}

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

TreeNode root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3, new TreeNode(4), new TreeNode(5))
);
Codec codec = new Codec();
string result = codec.serialize(root);
System.Console.WriteLine(result);

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

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

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

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

💡 Hint

Think about preorder traversal with '#' representing null nodes.

The serialization uses preorder traversal: root, left, right.

Null children are represented by '#'.

So the tree serializes as: 1 (root), 2 (left child), # (2's left null), # (2's right null), 3 (right child), 4 (3's left), # (4's left null), # (4's right null), 5 (3's right), # (5's left null), # (5's right null).

❓ Predict Output

intermediate

What is the deserialized tree's root value?

Given the serialized string "1,2,#,#,3,4,#,#,5,#,#" and the deserialize method below, what is the value of the root node after deserialization?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Codec {
    private int index = 0;
    private string[] nodes;

    public TreeNode deserialize(string data) {
        nodes = data.Split(',');
        index = 0;
        return helper();
    }

    private TreeNode helper() {
        if (index >= nodes.Length || nodes[index] == "#") {
            index++;
            return null;
        }
        TreeNode root = new TreeNode(int.Parse(nodes[index++]));
        root.left = helper();
        root.right = helper();
        return root;
    }
}

Codec codec = new Codec();
TreeNode root = codec.deserialize("1,2,#,#,3,4,#,#,5,#,#");
System.Console.WriteLine(root.val);

A 2

B 1

C 3

D 0

💡 Hint

The first value in the serialized string is the root's value.

The deserialize method reads the first value as the root node's value.

Since the first value is '1', the root node's value is 1.

🔧 Debug

advanced

Why does this deserialize method cause an error?

Consider this deserialize method. Why does it cause a runtime error when deserializing "1,2,#,#,3,4,#,#,5,#,#"?

DSA C#

public class Codec {
    private int index = 0;
    private string[] nodes;

    public TreeNode deserialize(string data) {
        nodes = data.Split(',');
        return helper();
    }

    private TreeNode helper() {
        if (index >= nodes.Length || nodes[index] == "#") {
            index++;
            return null;
        }
        TreeNode root = new TreeNode(int.Parse(nodes[index++]));
        root.left = helper();
        root.right = helper();
        return root;
    }
}

A helper() is missing a return statement

B nodes array is empty, causing null reference error

C int.Parse fails because nodes contain non-numeric characters

D index is not reset before calling helper(), causing index out of range error

💡 Hint

Check the value of index before starting recursion.

The index variable is not reset to 0 before starting the recursive helper calls.

If deserialize is called multiple times on the same Codec instance, index may be beyond the array length, causing an index out of range error.

❓ Predict Output

advanced

What is the output of this serialization with level order traversal?

Given the following serialization method using level order traversal (BFS), what is the output string for the tree below?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Codec {
    public string serialize(TreeNode root) {
        if (root == null) return "";
        var queue = new System.Collections.Generic.Queue<TreeNode>();
        queue.Enqueue(root);
        var result = new System.Text.StringBuilder();
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            if (node == null) {
                result.Append("#,");
                continue;
            }
            result.Append(node.val + ",");
            queue.Enqueue(node.left);
            queue.Enqueue(node.right);
        }
        return result.ToString().TrimEnd(',');
    }
}

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

TreeNode root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3, new TreeNode(4), new TreeNode(5))
);
Codec codec = new Codec();
string output = codec.serialize(root);
System.Console.WriteLine(output);

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

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

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

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

💡 Hint

Level order traversal visits nodes level by level, using '#' for null children.

The BFS traversal visits nodes in this order: 1, 2, 3, null, null, 4, 5, null, null, null, null.

Null children of 2 are represented by '#', similarly for 4 and 5.

🧠 Conceptual

expert

What is the minimum number of nodes in the serialized string of a binary tree with N nodes using preorder serialization with null markers?

Consider a binary tree with N nodes. Using preorder traversal serialization with '#' as null markers for missing children, what is the minimum length (number of elements) of the serialized string?

A 2 * N + 1

B 2 * N

C N + 1

D N

💡 Hint

Each node has two children; null children are marked with '#'.

In a binary tree with N nodes, there are N+1 null children in total.

Preorder serialization records each node and each null child.

So total elements = N (nodes) + (N+1) (nulls) = 2N + 1.

Practice

1. What is the main purpose of serialize and deserialize methods 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 from 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: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking serialization deletes nodes
• Assuming serialization finds tree height

2. Which of the following is the correct C# method signature for a serialize method that converts a binary tree root node to a string?

easy

A. public TreeNode Serialize(string data)

B. public void Serialize(TreeNode root)

C. public string Serialize(TreeNode root)

D. public int Serialize(TreeNode root)

Solution

1. Step 1: Identify return type for serialization

   Serialization converts a tree to a string, so the return type must be string.

2. Step 2: Check method parameters

   The method should take the root node of the tree as input, typically TreeNode root.

3. Final Answer:

   public string Serialize(TreeNode root) -> Option C

4. Quick Check:

   Serialize returns string from TreeNode [OK]

Hint: Serialize returns string, input is root node [OK]

Common Mistakes:

• Using void return type for serialize
• Confusing serialize with deserialize signature
• Returning int instead of string

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

medium

A. [5, 4, 3, 2, 1]

B. [2, 1, 4, 3, 5]

C. [2, 4, 1, 3, 5]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Reconstruct tree from preorder string

   Preorder: root=1, left subtree=2,#,# (2 with no children), right subtree=3,4,#,#,5,#,# (3 with left=4, right=5).

2. Step 2: Perform inorder traversal (left, root, right)

   Inorder: left subtree of 1 is 2, then root 1, then left subtree of 3 is 4, root 3, right subtree 5. So inorder is [2, 1, 4, 3, 5].

3. Final Answer:

   [2, 1, 4, 3, 5] -> Option B

4. Quick Check:

   Inorder matches reconstructed tree [OK]

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

Common Mistakes:

• Mixing preorder and inorder traversal orders
• Ignoring null markers '#' in deserialization
• Incorrectly assigning left and right children

4. Consider this deserialize method snippet in C#:

public TreeNode Deserialize(string data) {
  var nodes = data.Split(',');
  int index = 0;
  return DeserializeHelper(nodes, ref index);
}

private TreeNode DeserializeHelper(string[] nodes, ref int index) {
  if (index >= nodes.Length || nodes[index] == "#") {
    index++;
    return null;
  }
  TreeNode node = new TreeNode(int.Parse(nodes[index++]));
  node.left = DeserializeHelper(nodes, ref index);
  node.right = DeserializeHelper(nodes, ref index);
  return node;
}

What is the main bug if index was passed without ref keyword?

medium

A. The index will not update correctly across recursive calls, causing infinite recursion or wrong tree

B. The code will not compile due to missing ref keyword

C. The tree will deserialize correctly without any issue

D. The method will throw a NullReferenceException

Solution

1. Step 1: Understand passing index by reference

   Passing index by ref allows recursive calls to update the same variable, tracking position in the array.

2. Step 2: Effect of missing ref

   If index is passed by value, each recursive call gets a copy, so updates won't reflect outside, causing repeated processing of same nodes and infinite recursion or wrong tree.

3. Final Answer:

   The index will not update correctly across recursive calls, causing infinite recursion or wrong tree -> Option A

4. Quick Check:

   Missing ref causes index not to update globally [OK]

Hint: Pass index by ref to track position across recursion [OK]

Common Mistakes:

• Assuming code won't compile without ref
• Thinking tree deserializes correctly without ref
• Confusing NullReferenceException with index issue

5. You want to serialize a binary tree and then deserialize it back. Which approach below correctly handles trees with duplicate values and null nodes?

hard

A. Use preorder traversal with '#' for nulls and commas to separate nodes

B. Use inorder traversal without null markers

C. Use level order traversal but skip null nodes

D. Serialize only leaf nodes and ignore internal nodes

Solution

1. Step 1: Understand serialization requirements

   To handle duplicates and nulls, serialization must record node values and null positions explicitly.

2. Step 2: Evaluate options

   Preorder with '#' for nulls and commas as separators records structure and values including duplicates. Inorder without nulls loses structure. Level order skipping nulls loses position info. Serializing only leaves loses tree shape.

3. Final Answer:

   Use preorder traversal with '#' for nulls and commas to separate nodes -> Option A

4. Quick Check:

   Preorder + null markers preserves full tree [OK]

Hint: Use preorder + null markers to keep duplicates and structure [OK]

Common Mistakes:

• Skipping null nodes loses tree shape
• Using inorder without nulls loses structure
• Ignoring duplicate values in serialization