1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val) {
4
 *     this.val = val;
5
 *     this.left = this.right = null;
6
 * }
7
 */
8

9
/**
10
 * Encodes a tree to a single string.
11
 *
12
 * @param {TreeNode} root
13
 * @return {string}
14
 */
15
var serialize = function (root) {
16
  // Using Preorder traversal to create a string of BST
17
  // Preorder works in following way
18
  // root -> left -> right
19
  let preorder = [];
20

21
  function dfs(node) {
22
    if (node === null) return;
23
    // Get root value
24
    preorder.push(node.val);
25

26
    // Get All the Left values
27
    dfs(node.left);
28

29
    // Get all the right values
30
    dfs(node.right);
31
  }
32

33
  // call it with root
34
  dfs(root);
35

36
  // Turn into string and return it
37
  return preorder.join(",");
38
};
39

40
/**
41
 * Decodes your encoded data to tree.
42
 *
43
 * @param {string} data
44
 * @return {TreeNode}
45
 */
46
var deserialize = function (data) {
47
  if (data === "") return null;
48

49
  // Get numbers array from a string
50
  const preorder = data.split(",").map(Number);
51

52
  // using -Infinity and +Infinity as placeholder check
53
  function recur(lower = -Infinity, upper = Infinity) {
54
    // This condition useful for when we are filling left side of tree it'll avoid all the values greater then then its upper value by putting null init.
55
    if (preorder[0] < lower || preorder[0] > upper) return null;
56

57
    // If preorder become empty
58
    if (preorder.length === 0) return null;
59

60
    // Create a root node [shift method will change the original array]
61
    const root = new TreeNode(preorder.shift());
62

63
    // Here for left side of tree, we are using current root node's value as 'upper bound' (so higher values ignored).
64
    root.left = recur(lower, root.val);
65

66
    // Same as above for right side we are using root node's values as 'lower bound' (so lower values ignored);
67
    root.right = recur(root.val, upper);
68

69
    return root;
70
  }
71

72
  // Final root will be out BST
73
  return recur();
74
};
75

76
/**
77
 * Your functions will be called as such:
78
 * deserialize(serialize(root));
79
 */