Start learning free

LESSON 417 OF 535 · BINARY TREES

Serialize and Deserialize a Binary Tree in C++: O(n) Preorder with Markers

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 27

Guided

Ctrl + Enter to check

C++ · BINARY TREES

Serialize And Deserialize Binary Tree in C++, explained

Problem overview

The class Codec has two methods. serialize(root) takes the root of a binary tree, which may be empty, and returns a string. deserialize(data) takes a string made by serialize and returns the root of the same tree: same shape, same value in every node. The format of the string is up to you. The lesson provides TreeNode, a struct with an int val, pointers left and right, and a constructor TreeNode(int x) that sets both pointers to NULL.

The tests serialize a tree with one Codec, rebuild it with a second Codec, and print the result level by level, with null for a missing child. For root = [1,2,3,null,null,4,5], the rebuilt tree prints as [1,2,3,null,null,4,5].

Approach: preorder with a marker for every missing child

A list of values alone does not identify a tree: the values 1, 2, 3 could be a root with two children or a chain of three nodes. The string also has to say where each subtree ends.

The lesson writes the tree in preorder (a node, then its left subtree, then its right subtree) and writes # for every missing child. Because each empty child leaves a marker, there is only one tree that fits the string. A reader that follows the same preorder knows after every node that its left subtree comes next, and that a # ends a subtree. Commas separate the pieces, so a value such as -100 is read back whole.

For the tree in the first example, the string is 1,2,#,#,3,4,#,#,5,#,#. An empty tree is the single piece #.

Both directions visit each node once, so each runs in O(n). Another common format is level order, as the tests print, but the recursive preorder version is shorter to write.

Step by step

The lesson builds serialize first, then deserialize. Both work on a list of pieces kept as a member of the class.

Declare the list. The member vector<string> values holds the pieces. Every method of the class sees it, so the helpers can add to it and read from it.
Clear it. serialize starts with values.clear(), because each call builds its pieces from scratch.
Call write(root). This helper, written next, adds the pieces of the whole tree to values in preorder.
Glue the pieces with commas. Start a string data with values[0]. There is always a first piece, since even the empty tree is written as #.
Loop over the rest with i from 1 while i < values.size(). Starting at 1 puts a comma between pieces, never before the first or after the last.
Append a comma and values[i] to data with +=.
Return data.
Declare void write(TreeNode* node). It adds the pieces of the subtree under node.
Mark a missing child. If node == NULL, push_back("#"). Writing every empty child is what makes the string rebuildable.
Return right after the marker. An empty child has nothing under it.
Write the node's value as text with to_string(node->val). The node comes first: that is preorder.
Write the left subtree by calling write(node->left).
Write the right subtree with write(node->right).
Add the read position. A second member, int pos, is the index of the next piece deserialize reads.
Clear values again at the start of deserialize. It will hold the pieces of data.
Prepare the split. C++ strings have no split method, so create a stringstream stream(data) and a string piece.
Read the pieces. The loop while (getline(stream, piece, ',')) reads up to the next comma into piece and ends when nothing is left.
Store each piece with values.push_back(piece).
Set pos = 0, the first piece.
Return read(), a helper that reads one whole subtree starting at pos. Called here, it reads the whole tree.
Declare TreeNode* read(). It mirrors write: it reads pieces in the order they were written.
Take the next piece into string value and add 1 to pos. Each piece is read exactly once.
A # means an empty subtree. If value == "#", return NULL.
Otherwise make a node with new TreeNode(stoi(value)), kept in node. The minus sign belongs to the piece, so negative values come back.
Read the left subtree: node->left = read(). This call consumes all the pieces of the left subtree, markers included, and stops where the right subtree begins.
Read the right subtree the same way.
Return node.

The solution in C++

class Codec {
public:
    vector<string> values;
    int pos;

    void write(TreeNode* node) {
        if (node == NULL) {
            values.push_back("#");
            return;
        }
        values.push_back(to_string(node->val));
        write(node->left);
        write(node->right);
    }

    string serialize(TreeNode* root) {
        values.clear();
        write(root);
        string data = values[0];
        for (int i = 1; i < values.size(); i++) {
            data += "," + values[i];
        }
        return data;
    }

    TreeNode* read() {
        string value = values[pos];
        pos++;
        if (value == "#") {
            return NULL;
        }
        TreeNode* node = new TreeNode(stoi(value));
        node->left = read();
        node->right = read();
        return node;
    }

    TreeNode* deserialize(string data) {
        values.clear();
        stringstream stream(data);
        string piece;
        while (getline(stream, piece, ',')) {
            values.push_back(piece);
        }
        pos = 0;
        return read();
    }
};

Round trips through the code give these results, with the string on the left and the tree rebuilt from it on the right:

1,2,#,#,3,4,#,#,5,#,#  ->  [1,2,3,null,null,4,5]
#  ->  []
-1,0,#,-100,#,#,#  ->  [-1,0,null,null,-100]
7,#,#  ->  [7]
1,#,2,#,3,#,#  ->  [1,null,2,null,3]

The C++ details worth a closer look:

Numbers and text. to_string turns an int into a string, and stoi turns a string back into an int, including a leading minus sign. stoi throws an exception when the text is not a number, which can't happen with a string produced by serialize.
Building the comma piece. In "," + values[i], the left side is a const char* and the right side a std::string, and the + operator for that pair makes a new string. Two string literals added together, such as "," + "#", would not compile.
stringstream and getline. A stringstream reads from a string the way cin reads from the keyboard. getline with a third argument stops at that character instead of the end of the line. The comma is discarded, and the stream becomes false after the last piece. A string with no trailing comma still yields its last piece.
Members as shared state. values and pos let the recursive helpers share one list and one position without passing them around. Because serialize and deserialize both clear values first, one Codec can be used for many trees, one after another. Using it from two threads at once would not be safe.
pos has no initial value. The member is not set until deserialize assigns 0, which happens before read() runs. read() is not meant to be called on its own.
NULL and the == on text. value == "#" compares the contents of two strings, not their addresses, because value is a std::string.

Complexity

Time: O(n). write is called once for each of the n nodes and once for each of the n + 1 empty children, with constant work per call. Joining the pieces appends each one to the end of data once, which is O(n) overall for these short pieces. deserialize splits the string into the same number of pieces, and read consumes each piece once.

Space: O(n). The list holds 2n + 1 pieces and the string has a similar size. The recursion adds a stack as deep as the tree is tall, up to 400 levels in the lesson's inputs.

Edge cases and common mistakes

The empty tree. serialize(NULL) returns #, and deserialize("#") returns NULL. Skipping the marker for an empty tree would leave values[0] reading from an empty vector.
Negative and multi-digit values. Without separators, -1 followed by 0 could not be told apart from other splits. The commas keep each value whole, so -1,0,#,-100,#,#,# reads back exactly.
Leaving out the markers. A preorder list of values alone fits many trees. The markers are what pin the shape down.
Reading in a different order. read must take the left subtree before the right one, because write wrote them in that order.
Not returning after the marker. If write kept going after pushing # for a null node, it would use node->val on a null pointer.
Splitting on a different character. The separator in getline has to match the one used when gluing the pieces, here a comma.

Testing

Each pair shows the tree, the string that serialize produces, and the tree deserialize returns.

[1,2,3,null,null,4,5] gives 1,2,#,#,3,4,#,#,5,#,# and back to [1,2,3,null,null,4,5].
[] gives # and back to [].
[-1,0,null,null,-100] gives -1,0,#,-100,#,#,# and back to the same tree.
[7] gives 7,#,#.
[1,2,3] gives 1,2,#,#,3,#,#.
[1,null,2,null,3] gives 1,#,2,#,3,#,#.

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

Start learning free