Serialize and Deserialize Binary Tree in DSA Rust

Mental Model

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

Analogy: Like writing a family tree on paper with names and empty spots, then reading it back to draw the same tree again.

    1
   / \
  2   3
     / \
    4   5

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

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 to a string and then rebuild the exact same tree from that string

Step 1: Start serialization at root node 1

Serialized string so far: "1,"

Why: We record the root value first to start the string

Step 2: Serialize left child 2

Serialized string so far: "1,2,"

Why: We record left subtree values next

Step 3: Serialize left child of 2 which is null

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

Why: We mark null to remember no child here

Step 4: Serialize right child of 2 which is null

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

Why: We mark null to remember no child here

Step 5: Serialize right child 3

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

Why: We record right subtree values after left subtree

Step 6: Serialize left child 4 of node 3

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

Why: We continue preorder traversal

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

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

Why: Mark nulls to keep tree shape

Step 8: Serialize right child 5 of node 3 and its null children

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

Why: Complete serialization of entire tree

Step 9: Start deserialization from string

Reading "1" creates root node 1

Why: We rebuild tree from root value first

Step 10: Deserialize left subtree from next values "2,null,null"

Left child of 1 is node 2 with no children

Why: Nulls mark no children

Step 11: Deserialize right subtree from remaining values "3,4,null,null,5,null,null"

Right child of 1 is node 3 with children 4 and 5

Why: Rebuild right subtree recursively

Result:

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

Annotated Code

DSA Rust

use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn serialize(root: &Option<Box<TreeNode>>) -> String {
    fn helper(node: &Option<Box<TreeNode>>, s: &mut String) {
        match node {
            Some(n) => {
                s.push_str(&format!("{},", n.val)); // record node value
                helper(&n.left, s); // serialize left subtree
                helper(&n.right, s); // serialize right subtree
            }
            None => {
                s.push_str("null,"); // mark null for missing child
            }
        }
    }
    let mut result = String::new();
    helper(root, &mut result);
    result.pop(); // remove trailing comma
    result
}

fn deserialize(data: &str) -> Option<Box<TreeNode>> {
    fn helper(nodes: &mut VecDeque<&str>) -> Option<Box<TreeNode>> {
        if let Some(val) = nodes.pop_front() {
            if val == "null" {
                return None; // null means no node here
            }
            let val_num = val.parse::<i32>().unwrap();
            let mut node = Box::new(TreeNode::new(val_num));
            node.left = helper(nodes); // build left subtree
            node.right = helper(nodes); // build right subtree
            Some(node)
        } else {
            None
        }
    }
    let mut nodes: VecDeque<&str> = data.split(',').collect();
    helper(&mut nodes)
}

fn print_tree(root: &Option<Box<TreeNode>>) {
    fn helper(node: &Option<Box<TreeNode>>) {
        match node {
            Some(n) => {
                print!("{} -> ", n.val);
                helper(&n.left);
                helper(&n.right);
            }
            None => {
                print!("null -> ");
            }
        }
    }
    helper(root);
    println!("null");
}

fn main() {
    // Build tree: 1
    //           /   \
    //          2     3
    //               / \
    //              4   5
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode::new(2))),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode::new(4))),
            right: Some(Box::new(TreeNode::new(5))),
        })),
    }));

    let serialized = serialize(&root);
    println!("Serialized: {}", serialized);

    let deserialized = deserialize(&serialized);
    print!("Deserialized preorder traversal: ");
    print_tree(&deserialized);
}

s.push_str(&format!("{},", n.val));

record current node value in string

helper(&n.left, s);

serialize left subtree recursively

helper(&n.right, s);

serialize right subtree recursively

if val == "null" { return None; }

detect null marker to stop subtree

let mut node = Box::new(TreeNode::new(val_num));

create new node from parsed value

node.left = helper(nodes);

deserialize left subtree recursively

node.right = helper(nodes);

deserialize right subtree recursively

Output

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

Deserialized preorder traversal: 1 -> 2 -> null -> null -> 3 -> 4 -> null -> null -> 5 -> null -> null -> null

Complexity Analysis

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

Space: O(n) for the output string and recursion stack proportional to tree height

vs Alternative: Compared to storing tree as nested objects, serialization produces a flat string that is easier to save or send, with similar time but better portability

Edge Cases

Empty tree (root is None)

Serialization returns "null" and deserialization returns None

DSA Rust

if val == "null" { return None; }

Tree with only one node

Serialization returns "val,null,null" and deserialization rebuilds single node tree

DSA Rust

s.push_str(&format!("{},", n.val));

Tree with only left or only right children

Null markers correctly preserve missing children so tree shape is maintained

DSA Rust

s.push_str("null,");

When to Use This Pattern

When you need to save or send a tree structure and later rebuild it exactly, use serialize/deserialize pattern to convert between tree and string.

Common Mistakes

Mistake: Forgetting to add null markers for missing children during serialization
Fix: Always add "null" placeholders to keep tree shape during serialization

Mistake: Not consuming the serialized string in order during deserialization
Fix: Use a queue or iterator to process nodes in the exact serialized order

Summary

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

Use it when you want to save or transfer a tree structure exactly.

The key is to record null children so the tree shape is preserved.

Practice

1. What is the main purpose of serialize and deserialize functions for a binary tree?

easy

A. Sort the binary tree nodes in ascending order

B. Delete all nodes from the binary tree

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

D. Count the number of leaf nodes in the 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 tree -> Option C

4. Quick Check:

   Serialize/deserialize = convert tree to string and back [OK]

Hint: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking serialization deletes nodes
• Mixing serialization with counting nodes

2. Which of the following Rust function signatures correctly represents a serialize function for a binary tree node defined as Option?

easy

A. fn serialize(root: Option) -> String

B. fn serialize(root: &TreeNode) -> Vec<i32>

C. fn serialize(root: Box<TreeNode>) -> Option<String>

D. fn serialize(root: Option<TreeNode>) -> String

Solution

1. Step 1: Check parameter type

   The binary tree root is usually represented as Option in Rust to allow empty trees and ownership.

2. Step 2: Check return type

   Serialization returns a String representing the tree.

3. Final Answer:

   fn serialize(root: Option) -> String -> Option A

4. Quick Check:

   Serialize takes Option and returns String [OK]

Hint: Serialize takes Option, returns String [OK]

Common Mistakes:

• Using &TreeNode instead of Option
• Returning Vec<i32> instead of String
• Using Option<TreeNode> without Box

3. Given the following Rust code snippet for serialization using preorder traversal, what is the output string for the tree with root value 1, left child 2, and right child 3?

fn serialize(root: Option) -> String {
    fn helper(node: &Option, s: &mut String) {
        match node {
            Some(n) => {
                s.push_str(&n.val.to_string());
                s.push(',');
                helper(&n.left, s);
                helper(&n.right, s);
            }
            None => s.push_str("#,")
        }
    }
    let mut result = String::new();
    helper(&root, &mut result);
    result
}

medium

A. "1,2,3,#,#,#,#,"

B. "1,2,#,#,3,#,#,"

C. "1,#,2,#,3,#,#,"

D. "#,1,2,3,#,#,#,"

Solution

1. Step 1: Understand preorder traversal serialization

   The function visits root, then left subtree, then right subtree, adding values and '#' for nulls.

2. Step 2: Trace the tree nodes

   Root 1: add "1," Left child 2: add "2," Left of 2 is None: add "#," Right of 2 is None: add "#," Right child 3: add "3," Left of 3 is None: add "#," Right of 3 is None: add "#,"

3. Final Answer:

   "1,2,#,#,3,#,#," -> Option B

4. Quick Check:

   Preorder serialize = "1,2,#,#,3,#,#," [OK]

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

Common Mistakes:

• Forgetting to add '#' for null children
• Mixing preorder with inorder or postorder
• Missing commas between values

4. The following Rust deserialize function has a bug. What is the main issue?

fn deserialize(data: &str) -> Option {
    fn helper(vals: &mut std::str::Split<char>) -> Option {
        match vals.next() {
            Some("#") => None,
            Some(val) => {
                let node_val = val.parse().unwrap();
                Some(Box::new(TreeNode {
                    val: node_val,
                    left: helper(vals),
                    right: helper(vals),
                }))
            }
            None => None,
        }
    }
    helper(&mut data.split(","))
}

medium

A. The function does not consume all input values

B. The function does not handle None values correctly

C. The parse unwrap can panic if val is not a number or '#'

D. The split iterator includes an empty string at the end causing parse errors

Solution

1. Step 1: Analyze split behavior

   Splitting a string like "1,2,#,#,3,#,#," by ',' produces an extra empty string at the end.

2. Step 2: Understand impact on parsing

   The helper tries to parse this empty string as a number, causing a panic or error.

3. Final Answer:

   The split iterator includes an empty string at the end causing parse errors -> Option D

4. Quick Check:

   Trailing comma causes empty string in split [OK]

Hint: Trailing comma in split creates empty string; handle or trim [OK]

Common Mistakes:

• Ignoring trailing empty string from split
• Assuming parse unwrap is always safe
• Not checking for None before parsing

5. You want to serialize a binary tree and then deserialize it back. Which approach below ensures the deserialized tree is structurally identical to the original, even if node values can be negative or zero?

hard

A. Use preorder traversal with '#' for nulls and commas as separators

B. Use inorder traversal without null markers and space separators

C. Use postorder traversal with zero as null marker and no separators

D. Use level order traversal but skip null nodes in serialization

Solution

1. Step 1: Consider traversal and null markers

   Preorder traversal with explicit '#' markers for nulls preserves tree structure exactly.

2. Step 2: Consider node values and separators

   Using commas as separators avoids confusion with negative or zero values; zero cannot be used as null marker.

3. Step 3: Evaluate other options

   Inorder without nulls loses structure; postorder with zero marker confuses zero values; skipping nulls in level order loses position info.

4. Final Answer:

   Use preorder traversal with '#' for nulls and commas as separators -> Option A

5. Quick Check:

   Preorder + '#' + commas = exact tree [OK]

Hint: Preorder + '#' + commas preserves structure with any values [OK]

Common Mistakes:

• Using inorder without null markers loses structure
• Using zero as null marker confuses zero values
• Skipping nulls in level order loses node positions