js-datastructures-algorithm/data-structures/binary-search-tree/binary-search-tree.test.js at master · quangnd/js-datastructures-algorithm · 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
import test from 'ava'
import { BinarySearchTree } from './binary-search-tree'

test(`Should create empty BinarySearchTree`, t => {
  const bst = new BinarySearchTree()
  t.is(bst.root, null)
})

test(`Should insert a new node into BST with insert(val)`, t => {
  const bst = new BinarySearchTree()
  bst.insert(10)
  t.is(bst.root.value, 10)
  t.is(bst.root.left, null)
  t.is(bst.root.right, null)

  bst.insert(8).insert(13)
  t.is(bst.root.value, 10)
  t.is(bst.root.left.value, 8)
  t.is(bst.root.right.value, 13)

  bst.insert(6).insert(15)
  t.is(bst.root.value, 10)
  t.is(bst.root.left.left.value, 6)
  t.is(bst.root.right.right.value, 15)

  t.is(bst.insert(6), undefined)
  t.is(bst.insert(15), undefined)
})

test(`Should return undefined if not found any element with find(val)`, t => {
  const bst = new BinarySearchTree()
  t.is(bst.find(1), undefined)

  bst.insert(10).insert(8).insert(13).insert(6).insert(15).insert(7)
  t.is(bst.find(4), undefined)
})

test(`Should return element if found with find(val)`, t => {
  const bst = new BinarySearchTree()
  bst.insert(10).insert(8).insert(13).insert(6).insert(15).insert(7)
  t.is(bst.find(13).value, 13)
  t.is(bst.find(7).value, 7)
})

test(`Should return boolean if BST contains element or not with contains(val)`, t => {
  const bst = new BinarySearchTree()
  t.is(bst.contains(1), false)

  bst.insert(10).insert(8).insert(13).insert(6).insert(15).insert(7)
  t.is(bst.contains(13), true)
  t.is(bst.contains(100), false)
})

//=== TREE TRAVERSAL
//Test Input
/**
 *          10
 *     6          15
 *  3       8         20
 *       7     9
 *
 */
test(`Should return values of nodes visited with Breadth-First Search - BFS()`, t => {
  const bst = new BinarySearchTree()
  bst.insert(10).insert(6).insert(15).insert(3).insert(8).insert(20).insert(7).insert(9)

  t.is(JSON.stringify(bst.BFS()), JSON.stringify([10, 6, 15, 3, 8, 20, 7, 9]))
})

test(`Should return values of nodes visited with Deep-First Search Pre-Order - DFSPreOrder()`, t => {
  const bst = new BinarySearchTree()

  bst.insert(10).insert(6).insert(15).insert(3).insert(8).insert(20).insert(7).insert(9)
  t.is(JSON.stringify(bst.DFSPreOrder()), JSON.stringify([10, 6, 3, 8, 7, 9, 15, 20]))
})

test(`Should return values of nodes visited with Deep-First Search Post-Order - DFSPostOrder()`, t => {
  const bst = new BinarySearchTree()

  bst.insert(10).insert(6).insert(15).insert(3).insert(8).insert(20).insert(7).insert(9)
  t.is(JSON.stringify(bst.DFSPostOrder()), JSON.stringify([3, 7, 9, 8, 6, 20, 15, 10]))
})

test(`Should return values of nodes visited with Deep-First Search In-Order - DFSInOrder()`, t => {
  const bst = new BinarySearchTree()

  bst.insert(10).insert(6).insert(15).insert(3).insert(8).insert(20).insert(7).insert(9)
  t.is(JSON.stringify(bst.DFSInOrder()), JSON.stringify([3, 6, 7, 8, 9, 10, 15, 20]))
})