[Algorithm] Serialize and Deserialize Binary Tree

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

 

Define createNode function:

function createNode(val, left = null, right = null) {
  return {
    val,
    left,
    addLeft(leftKey) {
      return this.left = leftKey ? createNode(leftKey) : null;
    },
    right,
    addRight(rightKey) {
      return this.right = rightKey ? createNode(rightKey) : null;
    }
  };
}

 

Define a binary tree:

function createBT(rootKey) {
  const root = createNode(rootKey);
  return {
    root,
    nodes: [],
    serialize(node) {

    },
    deserialize(str) {

    }
  };
}

 

Construct the tree:

const tree = createBT("root");
const root = tree.root;
const left = root.addLeft("left");
root.addRight("right");
left.addLeft("left.left");
left.addRight("left.right");

 

Serialize the tree:

The idea to serialize a tree is using recsurice apporach, keep calling serialize function for the left side node, then keep calling serialize function for right side nodes.

In the end, we output the serialized nodes in string format.

    serialize(node) {
      if (node) {
        this.nodes.push(node.val);
        this.serialize(node.left);
        this.serialize(node.right);
      } else {
        this.nodes.push("#");
      }
      return this.nodes.join(" ");
    },

const ser = tree.serialize(root); // root left left.left # # # right # #

 

Deserialize tree:

By given the serialized tree, every time we calling recsurice, we are trying to create Node, then append its left and right node.

    deserialize(str) {
      
      function* getVals() {
        for (let val of str.split(" ")) {
          yield val;
        }
      }
      
      const helper = (pointer) => {
        let { value , done } = pointer.next();
        if (value === "#" || done) return null;

        let node = createNode(value);
        node.left = helper(pointer);
        node.right = helper(pointer);
        return node;
      };
      return helper(getVals());
    }

const dec = tree.deserialize(ser).left.left.val; // left.left

 

-----

function createNode(val, left = null, right = null) {
  return {
    val,
    left,
    addLeft(leftKey) {
      return this.left = leftKey ? createNode(leftKey) : null;
    },
    right,
    addRight(rightKey) {
      return this.right = rightKey ? createNode(rightKey) : null;
    }
  };
}

function createBT(rootKey) {
  const root = createNode(rootKey);
  return {
    root,
    nodes: [],
    serialize(node) {
      if (node) {
        this.nodes.push(node.val);
        this.serialize(node.left);
        this.serialize(node.right);
      } else {
        this.nodes.push("#");
      }
      return this.nodes.join(" ");
    },
    deserialize(str) {
      
      function* getVals() {
        for (let val of str.split(" ")) {
          yield val;
        }
      }
      
      const helper = (pointer) => {
        let { value , done } = pointer.next();
        if (value === "#" || done) return null;

        let node = createNode(value);
        node.left = helper(pointer);
        node.right = helper(pointer);
        return node;
      };
      return helper(getVals());
    }
  };
}
////////Construct the tree///////////
const tree = createBT("root");
const root = tree.root;
const left = root.addLeft("left");
root.addRight("right");
left.addLeft("left.left");
left.addRight("left.right");

///////////Serialize and deserialize//////////////
const ser = tree.serialize(root); // root left left.left # # # right # #
const dec = tree.deserialize(ser).left.left.val; // left.left
console.log(ser, dec)