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 {
    int value = stream.readInt();
    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:
      value = pickle.load(stream)
      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.