Serialize and Deserialize Binary Tree

Complete Data: 2020-12-23

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.

Clarification: The input/output 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.

Example

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

Solution

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

// print the tree in pre-order traversal and split node with ','.
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  return root
    ? [root.val, ...serialize(root.left), ...serialize(root.right)]
    : [null];
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const buildTree = (data) => {
    const val = data.pop();
    return val === null
      ? null
      : { val, left: buildTree(data), right: buildTree(data) };
  };

  return buildTree(data.reverse());
};

Complexity Analysis

• Time complexity: O(N)
• Space complexity: O(log(N))