Data-Structures/5-binary-search-tree.js at main · francomac/Data-Structures · 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

function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

BST.prototype.insert = function(value) {
  if (value <= this.value) {
    if (!this.left) this.left = new BST(value);
    else this.left.insert(value);
  }
  else if (value > this.value) {
    if (!this.right) this.right = new BST(value);
    else this.right.insert(value)
  }
}


let bst = new BST(50);

bst.insert(30)
bst.insert(70)
bst.insert(100)
bst.insert(60)
bst.insert(59)
bst.insert(20)
bst.insert(45)
bst.insert(35)
bst.insert(105)
bst.insert(10)

// console.log(bst.right.left.left) // 59
// console.log(bst.right.right) // 100
// console.log(bst.left.right.left) // 35

BST.prototype.contains = function(value) {
  if (value === this.value) return true;
  else if (value < this.value) {
    if (!this.left) return false;
    else return this.left.contains(value);
  }
  else if (value > this.value) {
    if (!this.right) return false;
    else return this.right.contains(value);
  }
}

// console.log(bst.contains(50)); // true
// console.log(bst.contains(15)); // false
// console.log(bst.contains(100)); // true

BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
  if (order === 'pre-order') iteratorFunc(this.value)
  if (this.left) this.left.depthFirstTraversal(iteratorFunc, order)
  if (order === 'in-order') iteratorFunc(this.value);
  if (this.right) this.right.depthFirstTraversal(iteratorFunc, order)
  if (order === 'post-order') iteratorFunc(this.value)
}

BST.prototype.breadFirstTraversal = function(iteratorFunc) {
  let queue = [this]

  while(queue.length) {
    let treeNode = queue.shift()

    iteratorFunc(treeNode);
    if (treeNode.left) queue.push(treeNode.left);
    if (treeNode.right) queue.push(treeNode.right);
  }
}

BST.prototype.getMinVal = function(iteratorFunc, node) {
  if (this.left) return this.left.getMinVal();
  else return this.value
}

BST.prototype.getMaxVal = function(iteratorFunc, node) {
  if (this.right) return this.right.getMaxVal();
  else return this.value
}

module.exports = {
  BST
}