Serialize and Deserialize Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Serialization Using Preorder Traversal

What is the output of the following Rust code that serializes a binary tree using preorder traversal with '#' as null marker and ',' as separator?

DSA Rust

use std::collections::VecDeque;

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

fn serialize(root: &Option<Box<TreeNode>>, output: &mut String) {
    match root {
        Some(node) => {
            output.push_str(&node.val.to_string());
            output.push(',');
            serialize(&node.left, output);
            serialize(&node.right, output);
        }
        None => {
            output.push_str("#,");
        }
    }
}

fn main() {
    let tree = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode {
                val: 4,
                left: None,
                right: None,
            })),
            right: Some(Box::new(TreeNode {
                val: 5,
                left: None,
                right: None,
            })),
        })),
    }));
    let mut output = String::new();
    serialize(&tree, &mut output);
    print!("{}", output);
}

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

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

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

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

💡 Hint

Think about preorder traversal: root, left subtree, right subtree. Null nodes are marked with '#'.

The code visits nodes in preorder and appends their values followed by a comma. Null children are represented by '#,'. The final string ends with a comma.

❓ Predict Output

intermediate

Result of Deserializing a Serialized String

Given the serialized string "1,2,#,#,3,4,#,#,5,#,#," representing a binary tree, what is the value of the root's right child's left node after deserialization?

DSA Rust

use std::collections::VecDeque;

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

fn deserialize(data: &mut VecDeque<&str>) -> Option<Box<TreeNode>> {
    if let Some(val) = data.pop_front() {
        if val == "#" {
            return None;
        }
        let val_num = val.parse::<i32>().unwrap();
        let left = deserialize(data);
        let right = deserialize(data);
        Some(Box::new(TreeNode { val: val_num, left, right }))
    } else {
        None
    }
}

fn main() {
    let serialized = "1,2,#,#,3,4,#,#,5,#,#,";
    let mut data: VecDeque<&str> = serialized.split(',').filter(|s| !s.is_empty()).collect();
    let root = deserialize(&mut data);
    if let Some(node) = root {
        if let Some(right) = node.right {
            if let Some(left_of_right) = right.left {
                print!("{}", left_of_right.val);
            }
        }
    }
}

A 2

B 5

C 3

D 4

💡 Hint

Follow the deserialization order and tree structure carefully.

The root's right child is 3, whose left child is 4. So the printed value is 4.

🔧 Debug

advanced

Identify the Bug in Serialization Code

What error will occur when running the following Rust serialization function for a binary tree?

DSA Rust

fn serialize(root: &Option<Box<TreeNode>>, output: &mut String) {
    if root.is_none() {
        output.push_str("#");
    } else {
        let node = root.as_ref().unwrap();
        output.push_str(&node.val.to_string());
        output.push(',');
        serialize(&node.left, output);
        serialize(&node.right, output);
    }
}

A The output string contains extra commas causing syntax errors.

B The output string misses commas after null markers, causing deserialization errors.

C The code causes infinite recursion.

D The code panics due to unwrap on None value.

💡 Hint

Check how null nodes are represented and separated.

Null nodes are marked with '#' but no comma is added after them, so the serialized string lacks proper separators, breaking deserialization.

🚀 Application

advanced

Number of Nodes After Deserialization

After deserializing the string "1,2,#,#,3,4,#,#,5,#,#," into a binary tree, how many nodes does the tree contain?

A 5

B 6

C 4

D 7

💡 Hint

Count all non-null nodes represented in the serialized string.

The tree has nodes with values 1, 2, 3, 4, and 5, totaling 5 nodes.

🧠 Conceptual

expert

Why Use Preorder Traversal for Serialization?

Why is preorder traversal commonly used for serializing and deserializing binary trees?

A Because preorder traversal visits the root before its children, allowing reconstruction of the tree structure in a single pass.

B Because preorder traversal visits nodes in sorted order, which simplifies deserialization.

C Because preorder traversal uses less memory than inorder or postorder traversals.

D Because preorder traversal avoids the need for null markers during serialization.

💡 Hint

Think about the order nodes are visited and how that helps rebuild the tree.

Preorder visits root first, so when deserializing, the root is known before its children, enabling correct tree reconstruction.

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