A cheat sheet for serializing and deserializing a binary tree in JavaScript

serializing a binary tree in javascript.md

About

I absolutely failed at a timed challenge on how to serialize and deserialize a binary tree in JS.

This is my way of compensating for that failure 🤦‍

Hopefully this helps someone!

Data structure

Type definition

For the TS nerds out there.

interface Node<T> {
  value: T;
  left: Node<T> | null;
  right: Node<T> | null;
}

Example structure

Here's an example structure compliant with the type definition above.

const tree = {
  value: 1,
  left: { 
    value: 2, 
    left: null, 
    right: { 
      value: 3, 
      left: null, 
      right: null 
    }
  },
  right: {
    value: 4,
    left: null,
    right: {
      value: 5,
      left: null,
      right: null
    }
  }
};

Visual

Here's what that tree looks like.

       1
     /    \
    2      4
      \      \
       3      5

Serializing

Here's a function which takes the binary tree from above and serializes it into a string.

const serialize = (node, result) => {
  const left = node.left == null ? 'null' : serialize(node.left, result);
  const right = node.right == null ? 'null' : serialize(node.right, result);

  const appendix = `${node.value} ${left} ${right}`;

  if (!result) {
    return appendix;
  }

  return `${result} ${appendix}`
};

Example output

With the example tree above, the output would be as follows

1 2 null 3 null null 4 null 5 null null

Deserialize

Here's how to take that above sting and convert it back into our runtime data type.

const deserialize = (str) => {
  const list = str.split((' '));

  const deserializeList = () => {
    if (list.length === 0) {
      return null;
    }

    const value = list.shift();

    if (value === "null") {
      return null;
    }

    return {
      value,
      left: deserializeList(),
      right: deserializeList(),
    }
  }
  
  return deserializeList();
}

Without mutation/reassignment

If for some reason you don't want to use mutation/reassignment you can use this reducer pattern.

const deserialize = (str) => {
  const deserializeList = (list) => {
    if (list.length === 0) {
      return [null, []];
    }

    const value = list[0];

    if (value === "null") {
      return [value, list.slice(1)];
    }

    const [left, remainder] = deserializeList(list.slice(1));
    const [right, finalRemainder] = deserializeList(remainder);

    return [{
      value,
      left,
      right,
    }, finalRemainder]
  }
  
  return deserializeList(str.split(' '))[0];
}