The challenge
Encode a binary tree as text and decode it into the same values and shape.
Values are signed integers. The decoder expects a valid complete stream from this serializer; it does not validate untrusted input.
Example
The sparse example [1,null,2,3] encodes as 1,#,2,3,#,#,#. An empty tree encodes as #.
Use the walkthrough below to inspect the input and each state change.
See Serialize tree, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Preorder plus a marker for every null child uniquely determines shape.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def serialize(root):
tokens = []
def write(node):
if node is None:
tokens.append("#")
return
tokens.append(str(node.value))
write(node.left)
write(node.right)
write(root)
return ",".join(tokens)
def deserialize(data):
# Input must be a complete stream produced by serialize.
tokens = iter(data.split(","))
def read():
token = next(tokens)
if token == "#":
return None
node = Node(int(token))
node.left = read()
node.right = read()
return node
return read()
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
string serialize(Node* root) {
vector<string> tokens;
function<void(Node*)> write = [&](Node* node) {
if (!node) { tokens.push_back("#"); return; }
tokens.push_back(to_string(node->value));
write(node->left); write(node->right);
};
write(root);
string out;
for (const string& token : tokens) {
if (!out.empty()) out += ',';
out += token;
}
return out;
}
Node* deserialize(const string& data) {
// Input must be a complete stream produced by serialize.
istringstream stream(data);
function<Node*()> read = [&]() -> Node* {
string token; getline(stream, token, ',');
if (token == "#") return nullptr;
Node* node = new Node(stoll(token));
node->left = read(); node->right = read();
return node;
};
return read();
}