1var assert = require('assert');
2
3function serialize(root) {
4  let string = '';
5
6  function generateStr(node) {
7    if (!node) {
8      string += 'e ';
9    } else {
10      string += node.val + ' ';
11      generateStr(node.left);
12      generateStr(node.right);
13    }
14  }
15
16  generateStr(root);
17
18  return string;
19}
20
21function deserialize(data) {
22  let nodes = data.split(' ');
23
24  function generateTree() {
25    let val = nodes.shift();
26
27    if (val === 'e') {
28      return null;
29    } else {
30      let node = new Node(Number(val));
31      node.left = generateTree();
32      node.right = generateTree();
33      return node;
34    }
35  }
36
37  return generateTree();
38}
39
40function Node(val) {
41  this.val = val;
42  this.left = null;
43  this.right = null;
44}
45
46// Regular binary trees
47var tree1 = new Node(4);
48tree1.left = new Node(1);
49tree1.right = new Node(3);
50
51var tree2 = new Node(5);
52tree2.left = new Node(10);
53tree2.left.left = new Node(17);
54tree2.left.right = new Node(3);
55tree2.right = new Node(8);
56
57// Binary search trees
58var tree3 = new Node(6);
59tree3.left = new Node(3);
60
61var tree4 = new Node(5);
62tree4.left = new Node(3);
63tree4.left.left = new Node(2);
64tree4.left.left.left = new Node(1);
65
66var tree5 = new Node(8);
67tree5.left = new Node(6);
68tree5.right = new Node(9);
69tree5.left.left = new Node(5);
70tree5.left.right = new Node(7);
71tree5.right.right = new Node(10);
72
73function treeCompare(a, b) {
74  if (!a && !b) {
75    return true;
76  } else if (!a || !b) {
77    return false;
78  } else {
79    return (
80      a.val === b.val &&
81      treeCompare(a.left, b.left) &&
82      treeCompare(a.right, b.right)
83    );
84  }
85}
86
87try {
88  const serialized = serialize(tree1);
89  assert.equal(serialized, '4 1 e e 3 e e ');
90
91  console.log('PASSED: ' + 'Test One');
92} catch (err) {
93  console.log(err);
94}
95
96try {
97  const serialized = serialize(tree2);
98  assert.equal(serialized, '5 10 17 e e 3 e e 8 e e ');
99
100  console.log('PASSED: ' + 'Test Two');
101} catch (err) {
102  console.log(err);
103}
104
105try {
106  const serialized = '5 10 17 e e 3 e e 8 e e ';
107  const deserialized = deserialize(serialized);
108
109  assert.equal(treeCompare(tree2, deserialized), true);
110
111  console.log('PASSED: ' + 'Test Three');
112} catch (err) {
113  console.log(err);
114}