297. Serialize and Deserialize Binary Tree

Description

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

My Solution

Source Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
let serialize = function(root) {
  //check for empty tree
  if (root === null) {
    return "[]";
  }

  let discovered = [root];
  let result = "[";

  while (discovered.length !== 0) {
    //at this point, all nodes in the queue are int he same level
    //we want to go level by level for a level order traversal
    let numInCurrentLevel = discovered.length;
    for (let i = 0; i < numInCurrentLevel; i++) {
      let node = discovered.shift();
      if (node) {
        result += "," + node.val;
        discovered.push(node.left);
        discovered.push(node.right);
      } else {
        result += ",null";
      }
    }
  }

  //remove trailing ',' for neatness
  result += "]";
  result = result.replace(",]", "]");

  return result;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
//idea: the serialized string was created through level order traversal
//make a queue and push an entire level to it before constructing the tree
let deserialize = function(data) {
  //check for empty tree string first
  if (data.length === 2) {
    return null;
  }

  //strip brackets and split into an array
  let arr = data.substring(1, data.length - 1).split(",");

  let queue = [];
  let tree = new TreeNode();
  tree.val = arr.shift();
  queue.push(tree);

  while (queue.length !== 0) {
    let node = queue.shift();
    //because of the way I did serialize(), every node explicitly has two child nodes
    //as a result, dequeing twice will never throw an exception
    let left = arr.shift();
    let right = arr.shift();

    if (left !== "null") {
      let leftChild = new TreeNode(left);
      queue.push(leftChild);
      node.left = leftChild;
    }
    if (right !== "null") {
      let rightChild = new TreeNode(right);
      queue.push(rightChild);
      node.right = rightChild;
    }
  }

  return tree;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

Analysis

leetcode's problem descrption says we can use any format we want we serialize the tree so my format is not 100% like the one they use. I really do not like how they're not explicit with their leaf nodes. I never liked it at all when I started working through these problems. So, my format explicitly shows null child nodes. It is uglier but I think it's way less confusing to look at.

serialize()

This is essentially just level-order traversal. The only change is that we build up a string containing all of the nodes' values as we traverse the tree. The algorithm is as follows: make a queue to hold discovered nodes. Start with the root and queue it. While there are still nodes in the queue, dequeue each one and enqueue its child nodes. Add the dequeued node's value to the serialized string. Repeat this process until the queue is empty.

The running time complexity is simply O(n) as we visit each node in the tree exactly once and queueing/dequeueing are both O(1) operations. The queue will only ever have at most two full levels of nodes in it at any given time, so space complexity is also simply O(n).

deserialize()

This is actually much easier than serialize(). We get a serialized string and create an array from it. We iterate over each element and create a new node and then queue its two children. We know for sure that the next two elements in the array correspond to the current node's children because I explicitly coded serialize() to always include null child nodes, regardless of position on the tree. I am quite happy I decided to do it this way.

We iterate over the array of node values exactly once. We also queue/dequeue n nodes once each. The running time complexity is O(n). The space complexity is also O(n) for the same reasons serialize() is.

Thoughts

This was a great problem. I am especially glad I picked this one to complete because now I have two great functions to use for my writeups. Lately I have been focusing on problems dealing with data structures and now I can easily create trees for my example sections.