1
exercism fetch typescript binary-search-tree

binary-search-tree.test.ts

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
import BinarySearchTree from './binary-search-tree'

function recordAllData(bst: BinarySearchTree) {
  const out: number[] = []
  bst.each((data: number) => out.push(data))
  return out
}

describe('BinarySearchTree', () => {
  it('should retain data', () => {
    expect(new BinarySearchTree(4).data).toEqual(4)
  })

  xit('should insert a lesser number to the left', () => {
    const four = new BinarySearchTree(4)
    four.insert(2)

    expect(four.data).toEqual(4)
    expect(four.left.data).toEqual(2)
  })

  xit('should insert the same number to the left', () => {
    const four = new BinarySearchTree(4)
    four.insert(4)

    expect(four.data).toEqual(4)
    expect(four.left.data).toEqual(4)
  })

  xit('should insert a greater number to the right', () => {
    const four = new BinarySearchTree(4)
    four.insert(5)

    expect(four.data).toEqual(4)
    expect(four.right.data).toEqual(5)
  })

  xit('should deal with a complex tree', () => {
    const four = new BinarySearchTree(4)
    four.insert(2)
    four.insert(6)
    four.insert(1)
    four.insert(3)
    four.insert(7)
    four.insert(5)

    expect(four.data).toEqual(4)
    expect(four.left.data).toEqual(2)
    expect(four.left.left.data).toEqual(1)
    expect(four.left.right.data).toEqual(3)
    expect(four.right.data).toEqual(6)
    expect(four.right.left.data).toEqual(5)
    expect(four.right.right.data).toEqual(7)
  })

  xit('should iterate over one element', () => {
    expect(recordAllData(new BinarySearchTree(4))).toEqual([4])
  })

  xit('should iterate over smaller element', () => {
    const four = new BinarySearchTree(4)
    four.insert(2)

    expect(recordAllData(four)).toEqual([2, 4])
  })

  xit('should iterate over larger element', () => {
    const four = new BinarySearchTree(4)
    four.insert(5)

    expect(recordAllData(four)).toEqual([4, 5])
  })

  xit('should iterate over complex tree', () => {
    const four = new BinarySearchTree(4)
    four.insert(2)
    four.insert(1)
    four.insert(3)
    four.insert(6)
    four.insert(7)
    four.insert(5)

    expect(recordAllData(four)).toEqual([1, 2, 3, 4, 5, 6, 7])
  })
})