Serialize and Deserialize Binary Tree in DSA Java - Build from Scratch

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you are working on a system that needs to save and load family trees. Each family tree is a binary tree where each person has at most two children. To save the tree to a file or send it over the network, you need to convert it into a string (serialize). Later, you want to rebuild the exact same tree from that string (deserialize).

🎯 Goal: You will build two functions: one to convert a binary tree into a string, and another to convert that string back into the original binary tree. This helps in saving and loading the tree easily.

📋 What You'll Learn

Create a binary tree node class called TreeNode with int val, TreeNode left, and TreeNode right.

Write a method serialize(TreeNode root) that returns a String representing the tree.

Write a method deserialize(String data) that returns the root TreeNode of the tree represented by the string.

Use preorder traversal (root, left, right) for serialization.

Represent null children with the string #.

Separate node values and null markers with commas.

💡 Why This Matters

🌍 Real World

Saving and loading hierarchical data like family trees, organization charts, or file directories in a compact string format.

💼 Career

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

1

Create the TreeNode class and sample tree

Create a class called TreeNode with an int val, and two TreeNode references called left and right. Then create a sample tree with root value 1, left child 2, and right child 3. The right child should have two children: left 4 and right 5.

DSA Java

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

Hint

Define the TreeNode class with the required fields and constructor. Then build the tree by linking nodes as described.

2

Add a helper variable for building the serialized string

Inside the Solution class, create a StringBuilder variable called sb to help build the serialized string. Initialize it as a new StringBuilder().

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Solution {
    public static TreeNode createSampleTree() {
        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);
        return root;
    }

    // Create a StringBuilder called sb
    // Your code here
}

Hint

Declare sb as a static variable inside the Solution class and initialize it.

3

Write the serialize method using preorder traversal

Write a static method called serialize that takes a TreeNode root and returns a String. Use preorder traversal (root, left, right). For each node, append its value to sb followed by a comma. For null nodes, append #,. Clear sb at the start. Return sb.toString() at the end.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Solution {
    public static TreeNode createSampleTree() {
        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);
        return root;
    }

    static StringBuilder sb = new StringBuilder();

    // Write serialize method here
    // Your code here
}

Hint

Use a helper method to do preorder traversal. Append #, for nulls and value, for nodes.

4

Write the deserialize method and print serialized string

Write a static method called deserialize that takes a String data and returns the root TreeNode. Split the string by commas into a Queue<String>. Use a helper method deserializeHelper that removes the first element from the queue. If it is #, return null. Otherwise, create a TreeNode with the integer value and recursively build left and right children. Finally, in the main method, create the sample tree, serialize it, print the serialized string, then deserialize it back and print the root value.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

import java.util.*;

public class Solution {
    public static TreeNode createSampleTree() {
        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);
        return root;
    }

    static StringBuilder sb = new StringBuilder();

    public static String serialize(TreeNode root) {
        sb.setLength(0);
        serializeHelper(root);
        return sb.toString();
    }

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

    // Write deserialize method and main method below
    // Your code here
}

Hint

Use a queue to process the serialized string tokens. Build the tree recursively. Then test by printing the serialized string and the root value after deserialization.

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