Algorithms/binarySearchTree.js at main · Felistus/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class Node {
  constructor(value) {
    this.value = value;
    this.right = null;
    this.left = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let currentRoot = this.root;
    while (true) {
      if (value === currentRoot.value) return undefined;
      if (value > currentRoot.value) {
        if (currentRoot.right) {
          currentRoot = currentRoot.right;
        } else {
          currentRoot.right = newNode;
          return this;
        }
      } else if (value < currentRoot.value) {
        if (currentRoot.left) {
          currentRoot = currentRoot.left;
        } else {
          currentRoot.left = newNode;
          return this;
        }
      }
    }
  }
  search(value) {
    if (!this.root) return "Empty Tree";
    let currentRoot = this.root;
    while (currentRoot) {
      if (value > currentRoot.value) {
        currentRoot = currentRoot.right;
      } else if (value < currentRoot.value) {
        currentRoot = currentRoot.left;
      } else {
        return `true: ${currentRoot.value} found in tree`;
      }
    }
    return `false: ${value} not in tree`;
  }
  // Breath-First Search : horizontal search
  BFS() {
    let node = this.root;
    let queue = [];
    let treeData = [];
    queue.push(node);
    while (queue.length) {
      node = queue.shift();
      treeData.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return treeData;
  }
  DFS_PreOrder() {
    let preOrderData = [];
    function traverse(node) {
      preOrderData.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return preOrderData;
  }
  DFS_PostOrder() {
    let postOrderData = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      postOrderData.push(node.value);
    }
    traverse(this.root);
    return postOrderData;
  }
  DFS_InOrder() {
    let inOrderData = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      inOrderData.push(node.value);
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return inOrderData;
  }
}
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
// console.log(tree.search(6));
// console.log(tree);
console.log(tree.BFS());
console.log(tree.DFS_PreOrder());
console.log(tree.DFS_PostOrder());
console.log(tree.DFS_InOrder());