Does the serialized string have to follow one fixed format?

No. Any representation is valid as long as serialization and deserialization follow the same format and the original tree can always be reconstructed.

Can preorder traversal reconstruct the tree without null markers?

Not for a general binary tree. Preorder values alone do not identify where missing left or right children occur.

Why does DFS deserialization build the left subtree before the right subtree?

The serialization follows Root → Left → Right. Therefore, after the root is read, the following tokens describe its left subtree before its right subtree.

How is an empty tree handled?

Both approaches represent an empty tree using "#". The same representation must be recognized during deserialization.

Which method uses less traversal memory?

DFS uses O(H) recursion space, while BFS uses O(W) queue space. DFS may use less memory for a wide tree, while BFS avoids recursion-depth concerns for a deeply skewed tree.

Serialize and Deserialize a Binary Tree

Design a method to serialize a binary tree into a string and another method to deserialize that string back into the original binary tree.

The serialized representation must preserve:

The value of every node
The exact structure of the tree
Every missing left and right child

After deserialization, the reconstructed tree must be structurally identical to the original tree.

In this article, tokens are separated using commas, but a trailing comma is not added. An empty tree is represented consistently as:

"#"

Example 1

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

Output: "1,2,#,#,3,4,#,#,5,#,#"

Explanation: Deserializing this string reconstructs root = [1, 2, 3, null, null, 4, 5].

Example 2

Input: root = []

Output: "#"

Explanation: The marker # represents an empty tree.

Practice it by yourself before moving onto the solutionTry now

Approach 1

A normal preorder traversal records nodes in the following order:

Root → Left → Right

However, node values alone are insufficient to preserve the structure.

For example, consider one tree in which node 2 is the left child of node 1 and another tree in which node 2 is the right child of node 1.

Both trees produce:

1,2

when missing children are ignored.

To remove this ambiguity, every null child is recorded using a special marker such as #.

The preorder sequence then contains enough information to identify both the node values and the missing-child positions.

During deserialization, the tokens are read in the same order. A value creates a node, while # represents a missing child. The left subtree is reconstructed before the right subtree, matching the preorder structure.

Algorithm

Serialization

The tree is traversed in preorder so that every node is recorded before its left and right subtrees.
When a null node is reached, # is appended so that the missing-child position is preserved.
When a non-null node is reached, its value is appended.
The left subtree is serialized before the right subtree.
All recorded tokens are joined using commas without adding a trailing comma.
For an empty root, "#" is returned.

Deserialization

The serialized string is split into tokens, and an index is maintained for the next unread token.
When # is encountered, null is returned because the current child position is empty.
Otherwise, a node is created using the current token.
The left subtree is reconstructed first because it appears before the right subtree in preorder.
The right subtree is then reconstructed using the remaining tokens.
The reconstructed node is returned to its parent call.

Dry Run

1 / 2

Diagram 1

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13private:
14    // Records nodes in preorder while preserving missing children.
15    void serializeHelper(TreeNode* root, string& data) {
16        // Record a marker when the current child is missing.
17        if (root == nullptr) {
18            data += "#,";
19            return;
20        }
21
22        data += to_string(root->val) + ",";
23
24        serializeHelper(root->left, data);
25        serializeHelper(root->right, data);
26    }
27
28    // Reconstructs one subtree from the preorder token sequence.
29    TreeNode* deserializeHelper(
30        vector<string>& tokens,
31        int& index
32    ) {
33        // A null marker means this child does not exist.
34        if (tokens[index] == "#") {
35            index++;
36            return nullptr;
37        }
38
39        TreeNode* root = new TreeNode(
40            stoi(tokens[index++])
41        );
42
43        // Preorder stores the left subtree before the right subtree.
44        root->left = deserializeHelper(tokens, index);
45        root->right = deserializeHelper(tokens, index);
46
47        return root;
48    }
49
50public:
51    // Converts the binary tree into a preorder string.
52    string serialize(TreeNode* root) {
53        string data;
54        serializeHelper(root, data);
55
56        return data;
57    }
58
59    // Reconstructs the original tree from the serialized string.
60    TreeNode* deserialize(string data) {
61        vector<string> tokens;
62        string token;
63        stringstream ss(data);
64
65        // Separate the serialized string into individual tokens.
66        while (getline(ss, token, ',')) {
67            tokens.push_back(token);
68        }
69
70        int index = 0;
71
72        return deserializeHelper(tokens, index);
73    }
74};
75
76// Prints the reconstructed tree in preorder for verification.
77void printPreorder(TreeNode* root) {
78    // Stop after reaching an empty subtree.
79    if (root == nullptr) {
80        return;
81    }
82
83    cout << root->val << " ";
84
85    printPreorder(root->left);
86    printPreorder(root->right);
87}
88
89// Builds a sample tree and verifies serialization and deserialization.
90int main() {
91    TreeNode* root = new TreeNode(1);
92    root->left = new TreeNode(2);
93    root->right = new TreeNode(3);
94    root->right->left = new TreeNode(4);
95    root->right->right = new TreeNode(5);
96
97    Solution solution;
98
99    string data = solution.serialize(root);
100    cout << data << endl;
101
102    TreeNode* newRoot = solution.deserialize(data);
103
104    printPreorder(newRoot);
105
106    return 0;
107}

Complexity Analysis

Let:

N denote the number of non-null nodes in the tree.
H denote the height of the tree.

A binary tree containing N nodes has N + 1 null-child positions. Therefore, the serialized sequence contains O(N) tokens in total.

Time Complexity: O(N) for both serialization and deserialization because every node and null-child marker is processed once.

Serialized Output Space: O(N) because the values and null markers are stored in the serialized string.

Auxiliary Space: O(H) because the recursive call stack contains at most one root-to-node path at a time.

For a balanced tree, H = O(log N). For a completely skewed tree, H = O(N).

Approach 2

The tree can also be serialized level by level using BFS.

A queue is used to process nodes from top to bottom. For every non-null node, its value is recorded and its two child positions are added to the queue. When a child is missing, # is recorded.

These null markers preserve the exact left and right positions of every child.

During deserialization, the first token is used to create the root. The remaining tokens are consumed in pairs for every parent removed from the queue:

The first token represents its left child.
The second token represents its right child.

The tree is therefore reconstructed level by level.

For the tree:

root = [1, 2, 3, null, null, 4, 5]

one valid BFS serialization is:

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

No trailing comma is added.

Algorithm

Serialization

If the tree is empty, "#" is returned.
The root is placed into a queue so that level-order processing can begin.
A non-null node’s value is recorded, and both of its child positions are added to the queue.
When a null position is removed from the queue, # is recorded.
Processing is continued until the queue becomes empty.
All recorded tokens are joined using commas without adding a trailing comma.

Deserialization

If the serialized string is "#", null is returned.
The root is created using the first token and is placed into a queue.
One parent is removed from the queue, and the next token is read for its left child.
If the token is not #, a left child is created and added to the queue.
The following token is read for the right child.
If that token is not #, a right child is created and added to the queue.
Processing is continued until all tokens have been consumed.
The reconstructed root is returned.

Dry Run

1 / 2

Diagram 1

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13public:
  // Converts the tree into a level-order string with null markers.
  string serialize(TreeNode* root) {
      // An empty tree is represented by a single null marker.
      if (root == nullptr) {
          return "#";
      }
20
      string data;
      queue<TreeNode*> q;
      q.push(root);
24
      // Process every tree position needed to preserve its structure.
      while (!q.empty()) {
          TreeNode* node = q.front();
          q.pop();
29
          // Preserve the position of a missing child.
          if (node == nullptr) {
              data += "#,";
              continue;
          }
35
          data += to_string(node->val) + ",";
37
          q.push(node->left);
          q.push(node->right);
      }
41
      return data;
  }
44
  // Reconstructs the tree level by level from the serialized string.
  TreeNode* deserialize(string data) {
      // A null marker represents an empty tree.
      if (data == "#") {
          return nullptr;
      }
51
      vector<string> tokens;
      string token;
      stringstream ss(data);
55
      // Separate the serialized string into individual tokens.
      while (getline(ss, token, ',')) {
          tokens.push_back(token);
      }
60
      TreeNode* root = new TreeNode(stoi(tokens[0]));
      queue<TreeNode*> q;
      q.push(root);
64
      int index = 1;
66
      // Attach the next two tokens as children of each queued node.
      while (!q.empty() && index < tokens.size()) {
          TreeNode* node = q.front();
          q.pop();
71
          // Create the left child only when its token is not null.
          if (tokens[index] != "#") {
              node->left = new TreeNode(
                  stoi(tokens[index])
              );
              q.push(node->left);
          }
          index++;
80
          // Create the right child only when its token is not null.
          if (
              index < tokens.size() &&
              tokens[index] != "#"
          ) {
              node->right = new TreeNode(
                  stoi(tokens[index])
              );
              q.push(node->right);
          }
          index++;
      }
93
      return root;
  }
96};
97
98// Prints the reconstructed tree in preorder for verification.
99void printPreorder(TreeNode* root) {
  // Stop after reaching an empty subtree.
  if (root == nullptr) {
      return;
  }
104
  cout << root->val << " ";
106
  printPreorder(root->left);
  printPreorder(root->right);
109}
110
111// Builds a sample tree and verifies serialization and deserialization.
112int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->right->left = new TreeNode(4);
  root->right->right = new TreeNode(5);
118
  Solution solution;
120

Complexity Analysis

Let:

N denote the number of non-null nodes in the tree.
W denote the maximum width of the tree, meaning the maximum number of nodes present at any level.

Time Complexity: O(N) for both serialization and deserialization because the sequence contains only O(N) node values and null markers.

Serialized Output Space: O(N) because the complete serialized representation is stored as a string.

Auxiliary Queue Space: O(W) because the queue may simultaneously store nodes from the widest part of the tree.

Since W ≤ N, the queue requires O(N) auxiliary space in the worst case.

The reconstructed tree itself requires O(N) space, but it is the required output of deserialization and is not counted as auxiliary space.

Both approaches preserve the complete structure of the binary tree.

The preorder DFS approach is often preferred because its recursive serialization and deserialization directly follow the structure of the tree.

The BFS approach is equally valid and may be easier to visualize because nodes are processed and reconstructed level by level.

Approach	Time Complexity	Auxiliary Traversal Space
Preorder DFS	`O(N)`	`O(H)`
Level Order BFS	`O(N)`	`O(W)`

Here:

N is the number of nodes.
H is the height of the tree.
W is the maximum width of the tree.

Both approaches additionally require O(N) space for the serialized representation.

Interview follow-up Questions

Node values alone do not preserve missing-child positions. Null markers distinguish a node having only a left child from a node having only a right child.

Serialize and Deserialize a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Serialization

Deserialization

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Serialization

Deserialization

Dry Run

Solution

Complexity Analysis

Both approaches preserve the complete structure of the binary tree.

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree

Serialize and Deserialize a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Serialization

Deserialization

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Serialization

Deserialization

Dry Run

Solution

Complexity Analysis

Both approaches preserve the complete structure of the binary tree.

Interview follow-up Questions

Why are null markers necessary during serialization?

Does the serialized string have to follow one fixed format?

Can preorder traversal reconstruct the tree without null markers?

Why does DFS deserialization build the left subtree before the right subtree?

How is an empty tree handled?

Which method uses less traversal memory?

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree