Why it matters
A program often needs to save a tree to a file, send it over a network, or keep it in a database. None of those places can hold a pointer. A pointer is a memory address that only means something inside one running program. To store a tree, you turn it into plain text, and to use it again you turn the text back into a tree. The first step is called serialize, and the second is called deserialize.
This lesson builds both steps for a binary tree. A binary tree is a set of nodes where each node holds one value and has at most two children, called the left child and the right child. The lesson covers the text format, the code that writes and reads it, and a set of tests on tree shapes that are easy to get wrong. The traversals that visit the nodes in order are covered in the earlier lessons of this module, so this lesson only uses one of them.
A tree is a shape, and a list of values is not
Start with a small example. Take this tree:
1
/ \
2 3
/
4The root is 1. It has two children, 2 on the left and 3 on the right. The node 3 has one child, 4, on its left side. Node 2 and node 4 have no children, and node 3 has no right child.
Now suppose you only write down the values in the order you visit them, starting at the root and going left before right. The list is 1, 2, 3, 4. That list does not tell you the shape. Node 4 could hang off the left of 3, or 4 could hang off the right of 3 if the tree were drawn differently, so the list alone is not enough. You need to record where the children are missing, too.
The fix is a marker. Use the text # to mean "there is no node here". Each time you reach an empty spot where a child could be, write #. With markers, the shape is fixed. Every node adds its value, and every missing child adds one #.
The idea: write the tree in preorder, with markers for empty slots
Preorder is a visiting order. You write the current node first, then the whole left subtree, then the whole right subtree. A subtree is any node together with everything below it. Here is the order for the example tree, with the markers included:
1, 2, #, #, 3, 4, #, #, #Read it slowly. The first token is 1, the root. The next token is 2, the left child of the root. The two # after it say that node 2 has no left child and no right child. The next token, 3, is the right child of the root. Then 4 is the left child of 3. Then three # tokens follow: one for the missing left child of 4, one for the missing right child of 4, and one for the missing right child of 3.
Count the tokens to check the format. A tree with n real nodes always has n + 1 markers, because a tree with n nodes has n + 1 empty spots where a child could be. The example has 4 real nodes and 5 markers, which makes 9 tokens. The count is useful later, because it tells you when a text is too short or too long.
Here are the two steps as plain rules:
- Serialize: visit the tree in preorder. Write the value of each real node. Write
#for each empty spot. Join all tokens with commas. - Deserialize: read the tokens from left to right. When a token is
#, the spot is empty. When a token is a number, create a node with that value, then read its left subtree and then its right subtree.
The deserialize rule works because it reads in exactly the same order that serialize wrote. The reader always knows that the next token belongs to the next spot in the walk. That is why the format needs both the values and the markers.
Why the markers are necessary
Consider two different trees. In the first, node 1 has only a left child, which is 2. In the second, node 1 has only a right child, which is 2. These are two different shapes. If you write only the values, both shapes give the same text. The next program prints that case and the marker version:
Values only (no markers), two different trees:
left child only: 1,2
right child only: 1,2
With markers:
left child only: 1,2,#,#,#
right child only: 1,#,2,#,#The values-only text is the same for both trees, so a reader cannot tell them apart. The text with markers is different for each tree, so it can be read back into the correct shape.
Writing the tree as text
The code below uses a Node struct with a value and two std::unique_ptr fields. A std::unique_ptr owns a heap object and deletes it when the owner goes away, so the tree cleans up after itself. The code uses std::string for text and std::vector for the list of tokens.
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(int v) : value{v} {}
};
// Walk the tree in preorder (node, left, right) and add one token per slot.
void write_tokens(const Node* current, std::vector<std::string>& tokens) {
if (current == nullptr) {
tokens.push_back("#");
return;
}
tokens.push_back(std::to_string(current->value));
write_tokens(current->left.get(), tokens);
write_tokens(current->right.get(), tokens);
}
std::string serialize(const Node* root) {
std::vector<std::string> tokens;
write_tokens(root, tokens);
std::string text;
for (std::size_t i = 0; i < tokens.size(); ++i) {
if (i > 0) {
text += ',';
}
text += tokens[i];
}
return text;
}The write_tokens function is recursive. It calls itself for the left child and then the right child, so the order of the two calls decides the order of the tokens. The const Node* parameter means the function only reads the tree and never changes it. The .get() call turns a std::unique_ptr into a plain pointer for reading.
The text is built with a loop that puts a comma between tokens but not before the first or after the last. That detail matters, because a stray comma at the end would create an extra empty token when the text is split again.
The next helper splits the text back into tokens:
std::vector<std::string> split(const std::string& text) {
std::vector<std::string> tokens;
std::string current;
for (char c : text) {
if (c == ',') {
tokens.push_back(current);
current.clear();
} else {
current += c;
}
}
tokens.push_back(current);
return tokens;
}The loop collects characters until it sees a comma, then saves the collected piece as one token. After the loop, the last piece is saved too. A text with no commas gives one token. An empty text gives one empty token, and the reader throws an error on it.
Here is what serialize produces for the example tree, and for a few other shapes. The tree is built with helper functions in main, and the output comes from running the program:
five nodes: 1,2,#,#,3,4,#,#,#
single node: 5,#,#
empty tree: #A single node has two missing children, so it writes 5,#,#. An empty tree is just one #, because there is one empty spot, which is the root itself.
Reading the tree back
Deserializing is the harder direction, because the code has to decide what each token means. The rule is simple once you see it: a # builds nothing, and a number builds a node and then reads two more subtrees. The reader keeps one shared position number, which says which token it is on next.
// pos is shared by every call, so each call moves it forward for the next one.
std::unique_ptr<Node> read_node(const std::vector<std::string>& tokens, std::size_t& pos) {
if (pos >= tokens.size()) {
throw std::runtime_error("ran out of tokens");
}
const std::string& token = tokens[pos++];
if (token == "#") {
return nullptr;
}
auto current = std::make_unique<Node>(std::stoi(token));
current->left = read_node(tokens, pos);
current->right = read_node(tokens, pos);
return current;
}
std::unique_ptr<Node> deserialize(const std::string& text) {
std::vector<std::string> tokens = split(text);
std::size_t pos = 0;
std::unique_ptr<Node> root = read_node(tokens, pos);
if (pos != tokens.size()) {
throw std::runtime_error("extra tokens after the tree");
}
return root;
}Trace the text 1,2,#,#,# by hand to see how the shared position works. The position starts at 0.
- Call for the root. Token 0 is
1, so position becomes 1 and a node with value 1 is made. - The root calls for its left child. Token 1 is
2, so position becomes 2 and a node with value 2 is made. - Node 2 calls for its left child. Token 2 is
#, so position becomes 3 and nothing is made. Node 2 then calls for its right child. Token 3 is#, so position becomes 4 and nothing is made. Node 2 is finished. - Back at the root, it calls for its right child. Token 4 is
#, so position becomes 5 and nothing is made. The root is finished. - Position is 5 and there are 5 tokens, so nothing is left over and the tree is complete.
The check at the end of deserialize matters. If the text has tokens the tree does not use, the position ends below the number of tokens. The check catches that, which a plain reader would silently accept. A text that is not a complete tree throws during the read itself.
Testing round trips on odd shapes
A round trip means you serialize a tree, deserialize the text, and serialize the result again. If the second text matches the first, the format and the two functions agree. The test does not compare pointers, because the rebuilt tree has new nodes at new addresses. It compares the text, which is the thing that matters.
Round trips work best on shapes that are likely to break the code. The test below uses six shapes:
int main() {
struct Case {
const char* name;
std::unique_ptr<Node> root;
};
std::vector<Case> cases;
cases.push_back({"empty tree", nullptr});
cases.push_back({"single node", leaf(5)});
cases.push_back({"five nodes", node(1, leaf(2), node(3, leaf(4), nullptr))});
cases.push_back({"left chain", node(1, node(2, node(3, nullptr, nullptr), nullptr), nullptr)});
cases.push_back({"right chain", node(1, nullptr, node(2, nullptr, node(3, nullptr, nullptr)))});
cases.push_back({"zero and negatives", node(0, leaf(-7), leaf(0))});
for (const Case& c : cases) {
std::string text = serialize(c.root.get());
std::unique_ptr<Node> copy = deserialize(text);
std::string again = serialize(copy.get());
std::cout << c.name << ": " << text << " round trip "
<< (text == again ? "ok" : "FAILED") << '\n';
}
return 0;
}The test uses two helpers that build small trees in one line each. They sit above main in the same file:
std::unique_ptr<Node> leaf(int v) {
return std::make_unique<Node>(v);
}
std::unique_ptr<Node> node(int v, std::unique_ptr<Node> l, std::unique_ptr<Node> r) {
auto n = std::make_unique<Node>(v);
n->left = std::move(l);
n->right = std::move(r);
return n;
}leaf(5) makes a node with no children. node(1, l, r) makes a node with value 1 and takes ownership of two subtrees, which may be nullptr. Running the test prints:
empty tree: # round trip ok
single node: 5,#,# round trip ok
five nodes: 1,2,#,#,3,4,#,#,# round trip ok
left chain: 1,2,3,#,#,#,# round trip ok
right chain: 1,#,2,#,3,#,# round trip ok
zero and negatives: 0,-7,#,#,0,#,# round trip okEach shape tests a different risk:
- The empty tree tests the case where the root itself is missing. The text must be one
#, and the reader must returnnullptrfor it. - The single node tests that a leaf with two markers reads back into one node and nothing else.
- The five-node tree tests a node that has one child on each side and a deeper node on one branch.
- The left chain and the right chain test a tree that is only one-sided. A chain of nodes all leaning one way is the most unbalanced shape, and bugs in the code for the right child or the left child show up here. The two chains differ only in which side the
#markers fall on, so they catch a reader that swaps left and right. - The zero and negative values test the number parsing. A value of
0is a real node, not a marker, and-7is a negative number that must parse correctly.
The test uses the text as the check. A stronger test also compares the two trees node by node, but the text check is enough here, because the text includes every value and every marker.
Bad input
The reader must reject text that is not a valid tree. The next program feeds three bad texts to deserialize and prints the error:
1,2 -> error: ran out of tokens
1,#,#,# -> error: extra tokens after the tree
12abc,#,# -> accepted, value 12The first text is cut short. The root reads 1, then its left child reads 2, then the left child of 2 has no token left, so the reader throws. The second text has one token too many, which the final check catches.
The third text shows a weakness. The reader used std::stoi, which converts the start of a string to a number and ignores the rest. The text 12abc is turned into 12 without an error. A strict reader would pass the optional second argument of std::stoi, which reports how many characters were used, and throw if the token has characters left over.
Common mistakes
Passing the position by value
The most common bug in this code is making the position a plain number instead of a reference. Here is a wrong version of the reader, taken from the mistakes program:
std::unique_ptr<Node> read_node_wrong(const std::vector<std::string>& tokens, std::size_t pos) {
if (pos >= tokens.size()) {
throw std::runtime_error("ran out of tokens");
}
const std::string& token = tokens[pos++];
if (token == "#") {
return nullptr;
}
auto current = std::make_unique<Node>(std::stoi(token));
current->left = read_node_wrong(tokens, pos);
current->right = read_node_wrong(tokens, pos);
return current;
}The function takes pos by value. Each call gets its own copy. When the left child moves the position forward, the root does not see the change, so the root reads the same token again for its right child. Running this reader on 1,2,#,#,# and writing the result back out prints:
input: 1,2,#,#,#
output: 1,2,#,#,2,#,#The reader raises no error, but the tree is wrong.
The output has a second 2 where the input has #. The round trip test catches this, because the two texts differ. Without a round trip test, this bug can look fine for simple inputs and fail only on larger ones.
Copying a unique_ptr
A std::unique_ptr cannot be copied, only moved. If you write n->left = child; with child as a named std::unique_ptr, the compiler rejects it. Here is the real message from g++ -std=c++20 -Wall, with the first lines shown and the long type names cut short:
copy_error.cpp:12:15: error: use of deleted function ... operator=(const std::unique_ptr<_Tp, _Dp>&)
12 | n->left = child;
| ^~~~~The fix is n->left = std::move(child);. The message is long, but the important part is the phrase "use of deleted function", which means the type cannot be copied.
Writing values only
Writing only the values without markers gives text that looks complete but cannot be read back into the right shape. The output in the earlier section shows two different trees giving the text 1,2. Always write the # markers, even when the tree looks simple.
Writing the children in a different order
Serialize and deserialize must agree on the order of children. If serialize writes the right subtree first and the reader expects the left subtree first, the shapes will come back wrong. Here is the output of a serializer that writes right before left, for the five-node tree:
five nodes, normal: 1,2,#,#,3,4,#,#,#
five nodes, right first: 1,3,#,4,#,#,2,#,#Both texts are valid, but a reader built for the normal order will read the second one as a different tree. Pick one order, document it, and use it in both directions.
Forgetting the leftover check
A reader without the check at the end accepts 1,#,#,# and quietly drops the last #. A text with extra data is almost always a sign of a bug in the writer or a damaged file. Check that the position equals the token count before you return.
Deep trees
The reader and the writer are recursive. Each level of the tree adds one call to the call stack. A tree that is a chain of many thousands of nodes makes the call stack very deep, and a deep enough chain can make the program crash. A stack of calls has a fixed size, so the safe fix for a very deep tree is to write the same walk with an explicit stack, as the iterative traversals lesson in this module does.
Practice
Exercise 1
Write the serialized text for a tree with root 7, left child 3, and right child 9. All three nodes are leaves.
Show the answer
The text is 7,3,#,#,9,#,#. The walk visits 7, then the left leaf 3 with its two markers, then the right leaf 9 with its two markers.
Exercise 2
Draw the tree that the text 4,#,8,#,# describes.
Show the answer
The root is 4. Its left spot is empty, because the next token is #. Its right child is 8. Node 8 has two empty spots, so it is a leaf. The tree is a root with only a right child. Drawn out, it looks like this:
4
\
8Exercise 3
Why does deserialize("5,6") throw an error?
Show the answer
The reader reads 5 as the root. It then reads 6 as the left child, and it wants two more tokens for the children of 6. There are none left, so the reader throws ran out of tokens. The text has no markers, so it does not say where the missing children are.
Exercise 4
Write a function count_nodes that takes the serialized text and returns how many real nodes it has. Do not build the tree.
Show the answer
Split the text into tokens, then count the tokens that are not #. The program's answer is:
int count_nodes(const std::string& text) {
int count = 0;
for (const std::string& token : split(text)) {
if (token != "#") {
++count;
}
}
return count;
}On 1,2,#,#,3,4,#,#,# it returns 4, which matches the number of real nodes.
Exercise 5
A writer produces the text 1,#,2,#,# for a tree. Is the text valid? If yes, which tree is it?
Show the answer
It is valid. The reader takes 1 as the root, then the left child is #, so the root has no left child. The right child is 2, which has two markers, so it is a leaf. The tree is a root 1 with only a right child 2, and serializing it again gives the same text.
Summary
- Serialize writes a tree in preorder, with
#for each missing child, and joins the tokens with commas. - The markers are needed. Values alone give the same text for different shapes.
- Deserialize reads the tokens in the same order, using one shared position that moves forward.
- Check that the reader used every token, and that it did not run out early.
- Test a round trip on empty, single, chain and negative-value trees, and compare the texts.
- Pass the position by reference, not by value, or the reader rebuilds the wrong tree.