javascript-algorithms/test/data-structures/binary-search-tree.spec.js at master · BIO2CS/javascript-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
'use strict';

var mod = require('../../src/data-structures/binary-search-tree.js');
var Node = mod.Node;
var BinaryTree = mod.BinaryTree;

describe('Node', function () {
  it('should be a constructor function', function () {
    expect(typeof Node).toBe('function');
  });
});

describe('Binary Tree', function () {
  it('should be a constructor function', function () {
    expect(typeof BinaryTree).toBe('function');
  });
  it('should start with null root', function () {
    expect(new BinaryTree()._root).toBe(null);
  });
  it('should insert and remove single node properly', function () {
    var bTree = new BinaryTree();
    bTree.insert(15);
    var node = bTree.find(15);
    bTree.remove(node);
    expect(bTree._root).toBe(null);
  });
  it('should remove root and replace with valid child', function () {
    var bTree = new BinaryTree();
    bTree.insert(15);
    bTree.insert(30);
    bTree.insert(45);
    var node = bTree.find(15);
    bTree.remove(node);
    expect(bTree._root.value).toBe(30);
  });
  it('should insert multiple nodes properly', function () {
    var bTree = new BinaryTree();
    bTree.insert(10);
    bTree.insert(5);
    bTree.insert(15);
    bTree.insert(4);
    bTree.insert(6);
    bTree.insert(14);
    bTree.insert(16);
    var leftRootChild = bTree._root._left;
    var rightRootChild = bTree._root._right;
    expect(bTree._root.value).toBe(10);
    expect(leftRootChild.value).toBe(5);
    expect(rightRootChild.value).toBe(15);
    expect(leftRootChild._left.value).toBe(4);
    expect(leftRootChild._right.value).toBe(6);
    expect(rightRootChild._left.value).toBe(14);
    expect(rightRootChild._right.value).toBe(16);
  });
  it('should remove multiple nodes properly', function () {
    var bTree = new BinaryTree();
    bTree.insert(10);
    bTree.insert(5);
    bTree.insert(15);
    bTree.insert(4);
    bTree.insert(6);
    bTree.insert(7);
    bTree.insert(14);
    bTree.insert(16);
    var leftRootChild = bTree._root._left;
    var rightRootChild = bTree._root._right;
    var sixteen = bTree.find(16);
    bTree.remove(sixteen);
    expect(bTree._root.value).toBe(10);
    expect(leftRootChild.value).toBe(5);
    expect(rightRootChild.value).toBe(15);
    expect(leftRootChild._left.value).toBe(4);
    expect(leftRootChild._right.value).toBe(6);
    expect(leftRootChild._right._right.value).toBe(7);
    expect(rightRootChild._left.value).toBe(14);
    expect(rightRootChild._right).toBe(null);
    var fourteen = bTree.find(14);
    bTree.remove(fourteen);
    expect(rightRootChild._left).toBe(null);
    var five = bTree.find(5);
    bTree.remove(five);
    expect(leftRootChild.value).toBe(6);
    expect(leftRootChild._left.value).toBe(4);
    expect(leftRootChild._right.value).toBe(7);
  });
});