Start learning free

LESSON 425 OF 543 · BINARY TREES

Serialize and Deserialize Binary Tree in Rust: O(n) Preorder

Practice O(n) Read the full explanation

Serializing a tree turns it into a string, so it can be saved in a file or sent over a network. Deserializing rebuilds the same tree from that string.

Implement the class Codec:

serialize(root) gets the root of a binary tree, which may be empty, and returns a string.
deserialize(data) gets a string made by serialize and returns the root of the same tree: the same shape, with the same value in every node.

The string's format is up to you. The tests serialize each tree with one Codec, rebuild it with a second Codec's deserialize, and print the rebuilt tree level by level, from left to right, with null where a child is missing and the trailing nulls left out. The trees below are written the same way. serialize must return a string. The starter code spells these names the way your language does.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
    1
   / \
  2   3
     / \
    4   5

Explanation: One string that works lists the nodes in preorder, with # for a missing child: "1,2,#,#,3,4,#,#,5,#,#". Reading it back gives the same tree.

Example 2:

Input: root = []
Output: []
Explanation: The empty tree needs a string too, for example "#", and deserialize gives back an empty tree.

Example 3:

Input: root = [-1,0,null,null,-100]
Output: [-1,0,null,null,-100]
    -1
    /
   0
    \
   -100

Explanation: Values can be negative and have several digits. With commas between the pieces, as in "-1,0,#,-100,#,#,#", every value is read back whole.

Constraints:

The number of nodes in the tree is in the range [0, 2 * 10⁵].
Each node value is between -1000 and 1000.
The tree is at most 400 levels deep.

Note:

Both serialize and deserialize should run in O(n) time, where n is the number of nodes.

STEP 1 OF 23

Guided

Ctrl + Enter to check

RUST · BINARY TREES

Serialize And Deserialize Binary Tree in Rust, explained

Problem overview

A Codec turns a binary tree into a string and back. serialize takes the root of a tree, which may be empty, and returns a String. deserialize takes a string that serialize made and returns the root of the same tree, with the same shape and the same value in every node. The format of the string is up to you.

The lesson provides TreeNode, with the fields val, left and right, and TreeNode::new(val), which makes a node with no children. The tests serialize with one Codec and rebuild with a second one, so a Codec must not rely on anything it remembers from its own serialize call.

For the tree [1,2,3,null,null,4,5] the reference solution produces the string 1,2,#,#,3,4,#,#,5,#,#, and reading it back gives [1,2,3,null,null,4,5]. The empty tree becomes #, and [-1,0,null,null,-100] becomes -1,0,#,-100,#,#,#.

Approach: preorder with a marker for every missing child

A traversal on its own doesn't identify a tree: the values 1, 2 could be a left child or a right child. The fix is to write down the gaps too. Walk the tree in preorder, a node, then its left subtree, then its right subtree, and write # for every missing child. Now the string says exactly where each subtree ends.

Reading it back is the same walk in reverse. Take the next piece. If it is #, this subtree is empty. Otherwise it is a node's value: create the node, read its whole left subtree, then its whole right subtree. Each recursive call consumes exactly the pieces of one subtree, so when the left call returns, the position is right where the right subtree begins.

Commas between the pieces keep multi-digit and negative values whole: -100 is one piece, not four characters. Every piece is written once and read once, so both methods run in O(n).

Step by step

Declare the struct's fields. values is a Vec<String>, the pieces of the string, shared by both methods.
Add pos, a usize, the position of the next piece that deserialize reads.
new returns a Codec with an empty Vec::new() and pos set to 0, written as an expression with no semicolon.
serialize starts with a fresh list, so each call builds its pieces from scratch.
Call self.write(&root). The helper only reads the tree, so lending it is enough.
Return self.values.join(","), gluing the pieces into one string with commas between them.
Declare write as fn write(&mut self, node: &Option<Box<TreeNode>>). It changes self but only borrows the tree.
Match on node. A match must cover both cases of the Option.
The None arm pushes "#" as a String.
The Some(node) arm gets a block.
Push the node's value with node.val.to_string(). The node comes first: that is preorder.
Write the left subtree with self.write(&node.left).
Write the right subtree the same way.
In deserialize, split the input with data.split(','), turn each part into a String and collect them into self.values.
Reset pos to 0, the first piece.
Return self.read(), which rebuilds the whole tree.
Declare read as fn read(&mut self) -> Option<Box<TreeNode>>. It mirrors write.
Copy the next piece with self.values[self.pos].clone() into value, and then add 1 to self.pos. The clone means value doesn't borrow from self while the recursive calls change it.
If value is "#", return None: an empty subtree.
Otherwise create the node from value.parse().unwrap(), boxed, declared mut.
Set node.left to self.read(). That call takes every piece of the left subtree, markers included.
Set node.right the same way. Now pos is just past this node's whole subtree.
Return Some(node).

The solution in Rust

struct Codec {
    values: Vec<String>,
    pos: usize,
}

impl Codec {
    fn new() -> Self {
        Codec { values: Vec::new(), pos: 0 }
    }

    fn write(&mut self, node: &Option<Box<TreeNode>>) {
        match node {
            None => self.values.push(String::from("#")),
            Some(node) => {
                self.values.push(node.val.to_string());
                self.write(&node.left);
                self.write(&node.right);
            }
        }
    }

    fn serialize(&mut self, root: Option<Box<TreeNode>>) -> String {
        self.values = Vec::new();
        self.write(&root);
        self.values.join(",")
    }

    fn read(&mut self) -> Option<Box<TreeNode>> {
        let value = self.values[self.pos].clone();
        self.pos += 1;
        if value == "#" {
            return None;
        }
        let mut node = Box::new(TreeNode::new(value.parse().unwrap()));
        node.left = self.read();
        node.right = self.read();
        Some(node)
    }

    fn deserialize(&mut self, data: String) -> Option<Box<TreeNode>> {
        self.values = data.split(',').map(|piece| piece.to_string()).collect();
        self.pos = 0;
        self.read()
    }
}

Rust details worth a closer look:

Methods that change the codec. write and read take &mut self because they push to values or advance pos. The recursive calls are also self.write(...) and self.read(), with no extra borrowing to manage.
Why clone(). self.values[self.pos] is a String inside the vector, and it can't be moved out of the index. Cloning gives an owned copy, and self is free to change afterwards.
parse() and its type. value.parse().unwrap() has no annotation. Rust works out from TreeNode::new, which takes an i32, that it should parse an i32. unwrap panics if the text isn't a number, which can't happen with text serialize wrote: it contains only numbers and #.
Comparing a String with a literal. value == "#" compares the contents, so it works without converting either side.
split(','). It takes a char here and returns an iterator over &str parts. The map turns each into an owned String, and collect() builds the Vec<String> because self.values has that type.
Last expressions. self.values.join(","), self.read(), Some(node) and the struct in new have no semicolon, so they are the values returned.
Taking ownership of the tree. serialize receives root by value and lends it with &root. The tree is dropped when the method ends, which is fine because the string holds everything.

Complexity

Time: O(n) for both methods. serialize visits each node once and each missing child once, which is about 2n + 1 pieces, then joins them. deserialize splits the string once and reads each piece once.

Space: O(n). The list of pieces and the string are linear in the number of nodes, and the recursion is as deep as the tree, at most 400 levels in this lesson.

Edge cases and common mistakes

The empty tree. write pushes one #, so the string is #, and read returns None at once. The string is never empty, so splitting it always gives at least one piece.
Skipping the markers. Without #, the tree 1 with left child 2 and the tree 1 with right child 2 would both give 1,2. The markers are what make the string unambiguous.
No separator. Without commas, -100 can't be told apart from the pieces -1, 0, 0, and 12 from 1 followed by 2.
Stale state. serialize resets values, and deserialize overwrites values and resets pos. A codec used twice would otherwise append to the old pieces or start reading in the middle.
Reading in a different order. read has to take the left subtree before the right one, the order write used. Swapping the two assignments would rebuild a mirrored tree.
Negative values. The minus sign is part of the piece, so "-1".parse::<i32>() reads it back correctly.

Testing

Serializing each tree with one Codec and rebuilding it with another gives:

[1,2,3,null,null,4,5] becomes 1,2,#,#,3,4,#,#,5,#,# and comes back as [1,2,3,null,null,4,5].
[] becomes # and comes back as [].
[-1,0,null,null,-100] becomes -1,0,#,-100,#,#,# and comes back unchanged.
[7] becomes 7,#,#.
[1,2,null,3] becomes 1,2,3,#,#,#,# and comes back as [1,2,null,3].

Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free