Serialize and deserialize a binary tree

Hard TimeO(n) SpaceO(n)

Write a binary tree out as a string, and read that string back into an identical tree — identical in shape as well as in values, because several different trees hold the same values in the same order. Empty children have to be represented too, or the shape is lost, and an empty tree has to survive the round trip as well.

Examples

Example 1

Input
roundTrip()
Output
["4,2,1,#,#,3,#,#,7,6,#,#,9,#,#","4,2,1,#,#,3,#,#,7,6,#,#,9,#,#"]
The tree written out, read back, and written out again — the two strings match exactly.

Example 2

Input
node = buildTree().left
Output
"2,1,#,#,3,#,#"
2, then its left 1 with two missing children, then its right 3 with two more.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function serialize(node) {
  if (node === null) return "#";
  return node.val + "," + serialize(node.left) + "," + serialize(node.right);
}
function deserialize(data) {
  const tokens = data.split(",");
  let index = 0;
  function build() {
    const token = tokens[index];
    index++;
    if (token === "#") return null;
    const node = { val: Number(token), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}
function roundTrip() {
  const text = serialize(buildTree());
  return [text, serialize(deserialize(text))];
}
roundTrip();
Done

The first 10 calls, of 48. This one does not fit on a page.

Step through roundTrip() call by call

More like this

All binary trees examples (9) →