Serialize and Deserialize Binary Tree in DSA Rust - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start Serialization

↓

Visit Node

↓

Write Value

↓

Serialize Left

↓

Repeat

↓

End Serialization

↓

Start Deserialization

↓

Read Next Token

↓

Return None

↓

Deserialize Left

↓

Deserialize Right

↓

Return Node

↓

End Deserialization

Serialization visits each node in preorder, writing values or nulls; deserialization reads tokens to rebuild the tree recursively.

Execution Sample

DSA Rust

fn serialize(root: &Option<Box<TreeNode>>, output: &mut Vec<String>) {
    if let Some(node) = root {
        output.push(node.val.to_string());
        serialize(&node.left, output);
        serialize(&node.right, output);
    } else {
        output.push("null".to_string());
    }
}

This Rust function serializes a binary tree into a vector of strings using preorder traversal.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Serialized Output	Visual Tree State
1	Visit root node	1	root -> 1	["1"]	1 / \ 2 3
2	Visit left child	2	root.left -> 2	["1", "2"]	1 / \ 2 3
3	Visit left.left (null)	null	2.left -> null	["1", "2", "null"]	1 / \ 2 3
4	Visit left.right (null)	null	2.right -> null	["1", "2", "null", "null"]	1 / \ 2 3
5	Visit right child	3	root.right -> 3	["1", "2", "null", "null", "3"]	1 / \ 2 3
6	Visit right.left (null)	null	3.left -> null	["1", "2", "null", "null", "3", "null"]	1 / \ 2 3
7	Visit right.right (null)	null	3.right -> null	["1", "2", "null", "null", "3", "null", "null"]	1 / \ 2 3
8	Serialization complete	none	none	["1", "2", "null", "null", "3", "null", "null"]	1 / \ 2 3
9	Start deserialization	none	read token index = 0	none	none
10	Read token '1', create node 1	1	root = 1	none	1 / \ ? ?
11	Read token '2', create node 2	2	1.left = 2	none	1 / \ 2 ?
12	Read token 'null', left of 2 is None	null	2.left = None	none	1 / \ 2 ?
13	Read token 'null', right of 2 is None	null	2.right = None	none	1 / \ 2 ?
14	Read token '3', create node 3	3	1.right = 3	none	1 / \ 2 3
15	Read token 'null', left of 3 is None	null	3.left = None	none	1 / \ 2 3
16	Read token 'null', right of 3 is None	null	3.right = None	none	1 / \ 2 3
17	Deserialization complete	none	tree rebuilt	none	1 / \ 2 3

💡 All nodes and nulls processed; tree fully serialized and deserialized.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 8	After Step 10	After Step 14	Final
root	Some(1)	1	1	1	1	None	None	None
output	[]	["1"]	["1", "2"]	["1", "2", "null", "null", "3"]	["1", "2", "null", "null", "3", "null", "null"]	N/A	N/A	N/A
read_token_index	0	N/A	N/A	N/A	N/A	0	4	7
current_node	None	1	2	3	None	1	3	None

Key Moments - 3 Insights

Why do we write 'null' for missing children during serialization?

Writing 'null' marks where a child is missing, so during deserialization we know exactly where to stop and reconstruct the tree shape correctly. See execution_table rows 3,4,6,7.

How does deserialization know which token belongs to left or right child?

Deserialization reads tokens in preorder: node, left subtree, right subtree. Each recursive call consumes tokens in order, so left subtree tokens come before right subtree tokens. See execution_table rows 11-13 and 14-16.

What happens if the tree is empty (root is None)?

Serialization immediately writes 'null' and deserialization reads 'null' and returns None, representing an empty tree. This is the base case for recursion.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the serialized output?

A ["1", "2", "null", "null", "3"]

B ["1", "2", "3"]

C ["1", "null", "2", "3"]

D ["1", "2", "null"]

💡 Hint

Check the Serialized Output column at step 5 in execution_table.

At which step does deserialization create the right child node with value 3?

A Step 11

B Step 14

C Step 10

D Step 16

💡 Hint

Look at the Node Visited and Operation columns in execution_table for deserialization steps.

If we remove writing 'null' during serialization, what happens during deserialization?

A Deserialization will fail to reconstruct the tree shape correctly.

B Deserialization will work fine without changes.

C The tree will be serialized with extra nodes.

D The output will be shorter but correct.

💡 Hint

Refer to key_moments about why 'null' is needed and see execution_table rows 3,4,6,7.

Concept Snapshot

Serialize and Deserialize Binary Tree:
- Serialize: preorder traversal, write node values or 'null' for missing children.
- Deserialize: read tokens in order, recursively rebuild nodes or None.
- 'null' tokens mark missing children to preserve tree shape.
- Both processes use recursion and preorder order.
- Result: tree can be converted to string and rebuilt exactly.

Full Transcript

This visualization shows how to convert a binary tree into a list of strings and back. Serialization visits each node in preorder: it writes the node's value if it exists, or 'null' if the node is missing. This way, the exact shape of the tree is recorded. The execution table traces each step, showing which node is visited, what is written, and how the output grows. Deserialization reads these tokens in order, creating nodes or None accordingly, rebuilding the tree structure exactly. Key moments explain why 'null' is necessary and how the recursive reading works. The quiz tests understanding of the serialized output and deserialization steps. The snapshot summarizes the process simply.

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