Serialize and Deserialize Binary Tree in DSA C#

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact same tree from that string.

Analogy: Like writing a family tree on paper and later reading it to redraw the same family tree exactly as before.

    1
   / \
  2   3
     / \
    4   5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree into a string and then rebuild the same tree from that string

Step 1: Start serialization at root node 1

Serialized string: "1,"

Why: We record the root value first to know where the tree starts

Step 2: Serialize left child 2

Serialized string: "1,2,"

Why: We record left subtree values next to keep order

Step 3: Serialize left and right children of 2 which are null

Serialized string: "1,2,null,null,"

Why: We mark nulls to know where branches end

Step 4: Serialize right child 3

Serialized string: "1,2,null,null,3,"

Why: After left subtree, we serialize right subtree root

Step 5: Serialize left child 4 of node 3

Serialized string: "1,2,null,null,3,4,"

Why: Continue preorder traversal to left child

Step 6: Serialize left and right children of 4 which are null

Serialized string: "1,2,null,null,3,4,null,null,"

Why: Mark null children to keep structure

Step 7: Serialize right child 5 of node 3

Serialized string: "1,2,null,null,3,4,null,null,5,"

Why: Serialize right child after left subtree

Step 8: Serialize left and right children of 5 which are null

Serialized string: "1,2,null,null,3,4,null,null,5,null,null,"

Why: Mark null children to complete serialization

Step 9: Start deserialization from serialized string

Rebuild node 1

Why: We read root value first to start rebuilding

Step 10: Deserialize left child from next value 2

Rebuild node 2 as left child of 1

Why: Left subtree comes next in preorder

Step 11: Deserialize left and right children of 2 as null

Left and right of 2 are null

Why: Null markers tell us no children here

Step 12: Deserialize right child 3

Rebuild node 3 as right child of 1

Why: Right subtree comes after left subtree

Step 13: Deserialize left child 4 of 3

Rebuild node 4 as left child of 3

Why: Continue preorder deserialization

Step 14: Deserialize left and right children of 4 as null

Left and right of 4 are null

Why: Null markers show no children

Step 15: Deserialize right child 5 of 3

Rebuild node 5 as right child of 3

Why: Finish right subtree deserialization

Step 16: Deserialize left and right children of 5 as null

Left and right of 5 are null

Why: Null markers complete tree

Result:

Tree rebuilt exactly as original:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA C#

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

public class Codec {
    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        if (root == null) return "null,"; // mark null nodes
        return root.val + "," + serialize(root.left) + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        var nodes = new Queue<string>(data.Split(',', StringSplitOptions.RemoveEmptyEntries));
        return helper(nodes);
    }

    private TreeNode helper(Queue<string> nodes) {
        string val = nodes.Dequeue(); // get next value
        if (val == "null") return null; // null means no node
        TreeNode node = new TreeNode(int.Parse(val));
        node.left = helper(nodes); // build left subtree
        node.right = helper(nodes); // build right subtree
        return node;
    }
}

class Program {
    static void PrintTree(TreeNode root) {
        if (root == null) {
            Console.Write("null ");
            return;
        }
        Console.Write(root.val + " ");
        PrintTree(root.left);
        PrintTree(root.right);
    }

    static void Main() {
        TreeNode root = new TreeNode(1,
            new TreeNode(2),
            new TreeNode(3, new TreeNode(4), new TreeNode(5))
        );

        Codec codec = new Codec();
        string serialized = codec.serialize(root);
        Console.WriteLine("Serialized: " + serialized);

        TreeNode deserializedRoot = codec.deserialize(serialized);
        Console.Write("Deserialized preorder: ");
        PrintTree(deserializedRoot);
        Console.WriteLine();
    }
}

if (root == null) return "null,";

mark null nodes explicitly to preserve tree shape

return root.val + "," + serialize(root.left) + serialize(root.right);

preorder traversal: root, left subtree, right subtree

var nodes = new Queue<string>(data.Split(',', StringSplitOptions.RemoveEmptyEntries));

split serialized string into tokens for deserialization

string val = nodes.Dequeue();

read next node value or null marker

if (val == "null") return null;

null marker means no node here

TreeNode node = new TreeNode(int.Parse(val));

create node with current value

node.left = helper(nodes);

recursively build left subtree

node.right = helper(nodes);

recursively build right subtree

Output

Serialized: 1,2,null,null,3,4,null,null,5,null,null,

Deserialized preorder: 1 2 null null 3 4 null null 5 null null 

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) because the serialized string and recursion stack both grow with number of nodes

vs Alternative: Compared to storing only values without nulls, this method preserves exact tree shape but uses more space

Edge Cases

Empty tree (root is null)

Serialization returns "null," and deserialization returns null tree

DSA C#

if (root == null) return "null,";

Tree with only one node

Serializes single value with null children markers; deserializes back to single node

DSA C#

if (val == "null") return null;

Tree with only left or only right children

Null markers correctly preserve missing branches during serialization and deserialization

DSA C#

if (val == "null") return null;

When to Use This Pattern

When you need to save or transfer a tree structure exactly and rebuild it later, use serialize/deserialize with preorder and null markers to keep shape.

Common Mistakes

Mistake: Not marking null children during serialization
Fix: Add explicit null markers so deserialization knows where branches end

Mistake: Using inorder traversal for serialization
Fix: Use preorder traversal because it allows reconstructing tree uniquely with null markers

Summary

Converts a binary tree to a string and back to the same tree.

Use when you want to save or send a tree and restore it exactly later.

The key is preorder traversal with null markers to keep the tree shape.

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