Serialize and Deserialize Binary Tree in DSA Java

Mental Model

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

Analogy: Like writing a family tree on paper and later using that paper to redraw the same family tree exactly.

    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

Step 2: Serialize left subtree of node 1 (node 2)

Serialized string: "1,2,"

Why: We record left child value

Step 3: Serialize left and right children of node 2 (both null)

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

Why: We mark null children to keep tree shape

Step 4: Serialize right subtree of node 1 (node 3)

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

Why: We record right child value

Step 5: Serialize left child of node 3 (node 4)

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

Why: We record left child of node 3

Step 6: Serialize left and right children of node 4 (both null)

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

Why: Mark null children to keep structure

Step 7: Serialize right child of node 3 (node 5)

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

Why: Record right child of node 3

Step 8: Serialize left and right children of node 5 (both null)

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

Why: Mark null children to keep tree shape

Step 9: Start deserialization from serialized string

Tokens: [1,2,null,null,3,4,null,null,5,null,null]

Why: We split string to rebuild tree nodes

Step 10: Create root node 1

Tree: 1

Why: Root is first token

Step 11: Create left child node 2

Tree: 1
/ 
2

Why: Next token is left child

Step 12: Left and right children of 2 are null, so no nodes created

Tree unchanged

Why: Null tokens mean no child

Step 13: Create right child node 3

Tree: 1
/ \
2   3

Why: Next token is right child

Step 14: Create left child node 4 of node 3

Tree: 1
/ \
2   3
   /

Why: Next token is left child of 3

Step 15: Left and right children of 4 are null

Tree unchanged

Why: Null tokens mean no child

Step 16: Create right child node 5 of node 3

Tree: 1
/ \
2   3
   / \
  4   5

Why: Next token is right child of 3

Step 17: Left and right children of 5 are null

Tree unchanged

Why: Null tokens mean no child

Result:

Final tree reconstructed:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA Java

import java.util.*;

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

public class SerializeDeserializeBinaryTree {

    // Serialize tree to string using preorder traversal
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null,"); // mark null to keep structure
            return;
        }
        sb.append(node.val).append(","); // record node value
        serializeHelper(node.left, sb); // serialize left subtree
        serializeHelper(node.right, sb); // serialize right subtree
    }

    // Deserialize string back to tree
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("null")) {
            return null; // null means no node here
        }
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes); // build left subtree
        node.right = deserializeHelper(nodes); // build right subtree
        return node;
    }

    // Helper to print tree inorder for verification
    public void printTree(TreeNode root) {
        if (root == null) return;
        printTree(root.left);
        System.out.print(root.val + " ");
        printTree(root.right);
    }

    public static void main(String[] args) {
        SerializeDeserializeBinaryTree serDeser = new SerializeDeserializeBinaryTree();

        // Build tree: 1
        //           / \
        //          2   3
        //             / \
        //            4   5
        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);

        String serialized = serDeser.serialize(root);
        System.out.println("Serialized: " + serialized);

        TreeNode deserializedRoot = serDeser.deserialize(serialized);
        System.out.print("Deserialized inorder: ");
        serDeser.printTree(deserializedRoot);
        System.out.println();
    }
}

sb.append(node.val).append(",");

record current node value in serialization string

serializeHelper(node.left, sb);

serialize left subtree recursively

serializeHelper(node.right, sb);

serialize right subtree recursively

if (node == null) { sb.append("null,"); return; }

mark null nodes to preserve tree shape

String val = nodes.poll();

get next token from serialized data

if (val.equals("null")) { return null; }

null token means no node here

TreeNode node = new TreeNode(Integer.parseInt(val));

create node from token value

node.left = deserializeHelper(nodes);

build left subtree recursively

node.right = deserializeHelper(nodes);

build right subtree recursively

Output

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

Deserialized inorder: 2 1 4 3 5 

Complexity Analysis

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

Space: O(n) for the string storage and recursion stack in worst case

vs Alternative: Compared to storing tree as adjacency lists or other formats, preorder with null markers is simple and keeps exact shape with minimal overhead

Edge Cases

Empty tree (root is null)

Serialization returns "null," and deserialization returns null tree

DSA Java

if (node == null) { sb.append("null,"); return; }

Tree with single node

Serialization records node value and two null children; deserialization rebuilds single node

DSA Java

if (val.equals("null")) { return null; }

Tree with only left or only right children

Null markers preserve missing children so tree shape is exact

DSA Java

sb.append("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 recording null children during serialization
Fix: Add explicit null markers to keep tree shape during deserialization

Mistake: Using inorder traversal for serialization
Fix: Use preorder or postorder with null markers because inorder alone cannot reconstruct unique tree

Summary

It converts a binary tree into a string and back to the same tree.

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

The key is to record null children to keep the tree shape during reconstruction.

Practice

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

easy

A. Delete all nodes in a binary tree

B. Sort the nodes of a binary tree in ascending order

C. Find the height of a binary tree

D. Convert a binary tree to a string and back to a tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a binary tree into a string format so it can be stored or sent easily.

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 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 it deletes nodes
• Mixing with tree height calculation

2. Which of the following is the correct Java method signature for a serialize function that converts a binary tree to a string?

easy

A. public int serialize(TreeNode root)

B. public void serialize(TreeNode root)

C. public String serialize(TreeNode root)

D. public TreeNode serialize(String data)

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, so parameter is 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, takes root node as input [OK]

Common Mistakes:

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

3. Given the following code snippet for serialization using preorder traversal with '#' as null marker and ',' as separator, what is the output string for the tree below? Tree:

    1
   / \
  2   3
     / \
    4   5

Code snippet:

void serializeHelper(TreeNode root, StringBuilder sb) {
  if (root == null) {
    sb.append("#,");
    return;
  }
  sb.append(root.val).append(",");
  serializeHelper(root.left, sb);
  serializeHelper(root.right, sb);
}

medium

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

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

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

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

Solution

1. Step 1: Perform preorder traversal with null markers

   Visit root: 1, then left subtree: 2, left null (#), right null (#), then right subtree: 3, left: 4, left null (#), right null (#), right: 5, left null (#), right null (#).

2. Step 2: Build string with commas and '#' for nulls

   Concatenate values and null markers with commas: "1,2,#,#,3,4,#,#,5,#,#,"

3. Final Answer:

   1,2,#,#,3,4,#,#,5,#,#, -> Option B

4. Quick Check:

   Preorder + nulls = 1,2,#,#,3,4,#,#,5,#,#, [OK]

Hint: Preorder serialize: root,left,right with '#' for null [OK]

Common Mistakes:

• Missing null markers (#)
• Wrong traversal order
• Omitting trailing commas

4. Identify the bug in the following deserialize method that reconstructs a binary tree from a serialized string using preorder traversal with '#' as null marker:

int index = 0;
TreeNode deserialize(String data) {
  String[] nodes = data.split(",");
  if (nodes[index].equals("#")) {
    index++;
    return null;
  }
  TreeNode root = new TreeNode(Integer.parseInt(nodes[index++]));
  root.left = deserialize(data);
  root.right = deserialize(data);
  return root;
}

medium

A. The index variable should be static or global to maintain state across recursive calls

B. The split method should use ";" instead of ","

C. The method should return a String instead of TreeNode

D. The base case should check for empty string instead of "#"

Solution

1. Step 1: Understand index usage in recursion

   The index variable tracks position in nodes array. It must keep its value across recursive calls to move forward correctly.

2. Step 2: Identify scope problem

   Here, index is a local variable inside the method, so it resets to 0 on each call, causing infinite recursion or wrong tree.

3. Final Answer:

   The index variable should be static or global to maintain state across recursive calls -> Option A

4. Quick Check:

   Index must persist across calls [OK]

Hint: Index must be shared across recursion, use class/global variable [OK]

Common Mistakes:

• Making index local causing reset each call
• Wrong delimiter in split
• Incorrect return type

5. You want to serialize a binary tree and then deserialize it back. However, your tree contains integer values that can be negative, zero, or positive. Which approach below correctly handles all integer values including negatives during serialization and deserialization?

hard

A. Use preorder traversal with ',' as separator and '#' for nulls; parse integers with Integer.parseInt during deserialization

B. Use inorder traversal without null markers; split by spaces; parse integers with Integer.parseInt

C. Use level order traversal but skip null nodes; separate values by commas; parse integers with Integer.parseInt

D. Serialize only positive values and ignore negatives; use preorder traversal

Solution

1. Step 1: Choose traversal and null markers

   Preorder traversal with '#' for nulls ensures structure is preserved, including negative and zero values.

2. Step 2: Parse integers correctly

   Integer.parseInt handles negative, zero, and positive integers correctly during deserialization.

3. Final Answer:

   Use preorder traversal with ',' as separator and '#' for nulls; parse integers with Integer.parseInt during deserialization -> Option A

4. Quick Check:

   Preorder + '#' + Integer.parseInt handles all integers [OK]

Hint: Use preorder + '#' + Integer.parseInt for all integer values [OK]

Common Mistakes:

• Skipping null markers causing wrong tree
• Ignoring negative values
• Using traversal without nulls losing structure