Serialize and Deserialize Binary Tree

Loading...LeetCode

Problem

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 1:

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

Example 2:

Input: root = []
Output: []

Pseudocode

- order of output is breath first
    - push nodes into queue and serialize values
    - remove any null values from the end of array
    - stringify array 

- parse input as into array
    - takes first three vals, as root, left, right
    - if values of left and right child exist
        - push them back into queue for their child nodes to be added if available

Solution

var serialize = function (root) {
  let output = [];
  let queue = root ? [root] : [];

  while (queue.length) {
    let node = queue.shift();

    if (node) {
      output.push(node.val);

      queue.push(node.left || null);
      queue.push(node.right || null);
    } else {
      output.push(null);
    }
  }

  while (output[output.length - 1] === null) {
    output.pop();
  }

  return JSON.stringify(output);
};

var deserialize = function (data) {
  const arr = JSON.parse(data);

  if (!arr.length) return null;

  const root = new TreeNode(arr.shift());
  const queue = [root];

  while (queue.length) {
    let node = queue.shift(),
      val;

    node.left = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;
    node.right = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -