# Serialize and Deserialize a Binary Tree

## Problem Statement

Given a binary tree, serialize and deserialize the binary tree.

• Serialize: Write the tree into a file.
• Deserialize: Read the tree from a file and reconstruct the binary tree into memory.

## Sample Test Cases

Input 1:

Output 1:
[1,2,3,null,null,4,5]

Input 2: []

Output 2:
[] // Empty tree

## Depth First Search Traversal-based Approach

We can solve this problem with a Depth First Search Traversal-based algorithm. The idea is to perform a DFS on the tree and serialize individual nodes to the output stream recursively. The traversal used here will be a pre-order traversal. To help in the process of deserializing the tree, we will use some marker variables to represent a null pointer.

Consider the above image, in this binary tree, the marker Mi represents the null nodes which make the process of deserializing the binary tree easier. The numbering of the markers merely represents the relative positioning of the marker with respect to each other.

The serialized tree, of the above binary tree, would look like this image.
During deserializing the tree, we will make a new node for every node which is not a marker node, while doing a pre-order traversal on the tree.

### C++ Code

```const int MARKER = INT_MIN
void serialize(TreeNode * node, ostream & sstream) {
if (node == nullptr) {
sstream.write((char * ) & MARKER, sizeof(MARKER));
return;
}
sstream.write((char * ) & node -> data, sizeof(node -> data));
serialize(node -> left, sstream);
serialize(node -> right, sstream);
}

TreeNode * deserialize(istream & sstream) {
if (sstream.eof() == true) {
return nullptr;
}
int value;
sstream.read((char * ) & value, sizeof(value));
if (value == MARKER) {
return nullptr;
}

TreeNode * newNode = new TreeNode(value);
newNode -> left = deserialize(sstream);
newNode -> right = deserialize(sstream);

return newNode;
}```

### Java Code

```static final int MARKER = Integer.MIN_VALUE;

public static void serialize(TreeNode node, ObjectOutputStream stream) throws java.io.IOException {
if (node == null) {
stream.writeInt(MARKER);
return;
}

stream.writeInt(node.data);
serialize(node.left, stream);
serialize(node.right, stream);
}

public static TreeNode deserialize(ObjectInputStream stream) throws java.io.IOException {
if (value == MARKER) {
return null;
}

TreeNode node = new TreeNode(val);
node.left = deserialize(stream);
node.right = deserialize(stream);
return node;
}```

### Python Code

```MARKER = 99999999999
def serialize(node, stream):
if node == None:
stream.dump(MARKER);
return
stream.dump(node.data);
serialize(node.left, stream)
serialize(node.right, stream)

def deserialize(stream):
try:
if value == MARKER:
return None
else:
node = BinaryTreeNode(data);
node.left = deserialize(stream)
node.right = deserialize(stream)
return node
except pickle.UnpicklingError:
return None```

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(logn)

## FAQs

### Q.1: What traversal algorithm is used in the approach for the above problem?

Ans. A Depth-First Search(DFS) is used to solve the above problem.

### Q.2: What is the significance of the marker variable in the above problem?

Ans. The marker variable is used to signify the null nodes of the tree, which helps in de-serializing the binary tree.

##### Previous Post ## Delete Node From Binary Search Tree

##### Next Post 