Serialize and Deserialize BST

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

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

Solution(javascript)

function TreeNode(val) {
  this.val = val
  this.left = null
  this.right = null
}


const serialize = (root) => {
  let current = [root]
  const result = []
  while (current.length) {
    const next = []
    current.forEach((node) => {
      result.push(node ? node.val : null)
      if (node) {
        next.push(node.left, node.right)
      }
    })
    current = next
  }
  return JSON.stringify(result)
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
const deserialize = (data = '') => {
  const list = JSON.parse(data)
  if (list.length === 0 || list[0] === null) {
    return null
  }
  const root = new TreeNode(list.shift())
  let current = [root]
  while (current.length > 0) {
    const next = []
    current.forEach((node) => {
      if (node !== null) {
        const leftValue = list.shift()
        const rightValue = list.shift()
        node.left = leftValue == null ? null : new TreeNode(leftValue)
        node.right = rightValue == null ? null : new TreeNode(rightValue)
        next.push(node.left, node.right)
      }
    })

    current = next
  }
  return root
}