Serialize and Deserialize Binary Tree in DSA C# - Build from Scratch

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you are building a simple app that needs to save and load a family tree. The family tree is a binary tree where each person has up to two children. To save the tree to a file or send it over the internet, you need to convert it into a string (serialize). Later, you want to rebuild the tree from that string (deserialize).

🎯 Goal: You will create a binary tree node class, write code to convert the tree into a string, and then write code to rebuild the tree from that string. This helps you understand how data structures can be saved and restored.

📋 What You'll Learn

Create a TreeNode class with int val, TreeNode left, and TreeNode right fields.

Create a sample binary tree with exact values and structure.

Write a Serialize method that converts the tree into a string using preorder traversal and # for null nodes.

Write a Deserialize method that rebuilds the tree from the serialized string.

Print the serialized string and verify the deserialized tree by printing its preorder traversal.

💡 Why This Matters

🌍 Real World

Saving and loading tree-like data structures such as family trees, organization charts, or decision trees in apps or games.

💼 Career

Understanding serialization and deserialization is important for software engineers working with data storage, networking, and APIs.

1

Create the TreeNode class and sample tree

Create a class called TreeNode with an int val field and two TreeNode fields called left and right. Then create a binary tree with root value 1, left child 2, and right child 3. The right child 3 should have two children: left child 4 and right child 5. Store the root in a variable called root.

DSA C#

// Define TreeNode class and create the tree
// Your code here

Hint

Define the TreeNode class with a constructor. Then create the tree exactly as described, linking children properly.

2

Add a helper variable for serialization

Create a StringBuilder variable called sb to help build the serialized string inside the Serialize method.

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3,
        new TreeNode(4),
        new TreeNode(5)
    )
);

// Create a StringBuilder called sb for serialization
// Your code here

Hint

Use StringBuilder sb = new StringBuilder(); to prepare for building the serialized string.

3

Write the Serialize and Deserialize methods

Write a method void Serialize(TreeNode node) that uses preorder traversal to add node values to sb, adding # for null nodes, separated by commas. Then write a method TreeNode Deserialize(Queue<string> nodes) that rebuilds the tree from the queue of node values, returning null for #. Use string.Split and Queue<string> to prepare the input for deserialization.

DSA C#

using System.Text;

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3,
        new TreeNode(4),
        new TreeNode(5)
    )
);

StringBuilder sb = new StringBuilder();

// Write Serialize(TreeNode node) method
// Write Deserialize(Queue nodes) method
// Your code here

Hint

Use preorder traversal for serialization. For deserialization, use a queue of strings and build the tree recursively.

4

Print the serialized string and verify deserialization

Call Serialize(root) to fill sb. Convert sb to a string called serialized and print it. Then create a Queue<string> from serialized.Split(',') (excluding empty entries). Call Deserialize with this queue to get TreeNode deserializedRoot. Finally, write a method void PrintPreorder(TreeNode node) that prints node values separated by spaces, skipping nulls, and call it with deserializedRoot.

DSA C#

using System.Text;
using System.Collections.Generic;

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3,
        new TreeNode(4),
        new TreeNode(5)
    )
);

StringBuilder sb = new StringBuilder();

void Serialize(TreeNode node)
{
    if (node == null)
    {
        sb.Append("#,");
        return;
    }
    sb.Append(node.val + ",");
    Serialize(node.left);
    Serialize(node.right);
}

TreeNode Deserialize(Queue nodes)
{
    if (nodes.Count == 0) return null;
    string val = nodes.Dequeue();
    if (val == "#") return null;
    TreeNode node = new TreeNode(int.Parse(val));
    node.left = Deserialize(nodes);
    node.right = Deserialize(nodes);
    return node;
}

// Call Serialize(root)
// Print serialized string
// Create queue from serialized string
// Call Deserialize(queue)
// Write PrintPreorder method
// Call PrintPreorder(deserializedRoot)
// Your code here

Hint

After serialization, print the string. Then deserialize and print preorder traversal to check correctness.

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