leetcode-practice/src/data_structure/binarySearchTree/binarySearchTree-implement.test.ts at main · sangtrandev00/leetcode-practice · 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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

import { describe, it, expect, beforeEach } from 'bun:test';
import { BinarySearchTree } from './binarySearchTree-implement';


describe('BinarySearchTree', () => {
    let tree: BinarySearchTree;

    beforeEach(() => {
        tree = new BinarySearchTree();
    });

    it('should insert nodes correctly', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.lookup(10)).toBeTruthy();
        expect(tree.lookup(5)).toBeTruthy();
        expect(tree.lookup(15)).toBeTruthy();
        expect(tree.lookup(20)).toBeFalsy(); // Not inserted
    });

    it('should lookup nodes correctly', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.lookup(10)).toEqual(expect.objectContaining({ value: 10 }));
        expect(tree.lookup(5)).toEqual(expect.objectContaining({ value: 5 }));
        expect(tree.lookup(15)).toEqual(expect.objectContaining({ value: 15 }));
        expect(tree.lookup(20)).toBeFalsy(); // Not inserted
    });

    it('should remove nodes correctly', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.remove(5)).toBeTruthy();
        expect(tree.lookup(5)).toBeFalsy(); // Should be removed
        expect(tree.remove(10)).toBeTruthy();
        expect(tree.lookup(10)).toBeFalsy(); // Should be removed
        expect(tree.remove(15)).toBeTruthy();
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
    });

    it('should handle removing a node with one child', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(12);
        expect(tree.remove(15)).toBeTruthy();
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
        expect(tree.lookup(12)).toEqual(expect.objectContaining({ value: 12 })); // Should still exist
    });

    it('should handle removing a node with two children', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(12);
        tree.insert(17);
        expect(tree.remove(15)).toBeTruthy();
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
        expect(tree.lookup(12)).toEqual(expect.objectContaining({ value: 12 })); // Should still exist
        expect(tree.lookup(17)).toEqual(expect.objectContaining({ value: 17 })); // Should still exist
    });

    it('should return false when removing a non-existent node', () => {
        tree.insert(10);
        expect(tree.remove(20)).toBeFalsy(); // Node does not exist
    });

    it('should remove a node with no children (leaf node)', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.remove(5)).toBeTruthy();
        expect(tree.lookup(5)).toBeFalsy(); // Should be removed
    });

    it('should remove a node with one child', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(12);
        expect(tree.remove(15)).toBeTruthy();
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
        expect(tree.lookup(12)).toEqual(expect.objectContaining({ value: 12 })); // Should still exist
    });

    it('should remove a node with two children', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(12);
        tree.insert(17);
        expect(tree.remove(15)).toBeTruthy();
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
        expect(tree.lookup(12)).toEqual(expect.objectContaining({ value: 12 })); // Should still exist
        expect(tree.lookup(17)).toEqual(expect.objectContaining({ value: 17 })); // Should still exist
    });

    it('should remove the root node with two children', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(12);
        tree.insert(17);
        expect(tree.remove(10)).toBeTruthy(); // Remove root
        expect(tree.lookup(10)).toBeFalsy(); // Should be removed
        expect(tree.lookup(12)).toEqual(expect.objectContaining({ value: 12 })); // Should still exist
        expect(tree.lookup(15)).toEqual(expect.objectContaining({ value: 15 })); // Should still exist
    });

    it('should remove the root node with one child', () => {
        tree.insert(10);
        tree.insert(5);
        expect(tree.remove(10)).toBeTruthy(); // Remove root
        expect(tree.lookup(10)).toBeFalsy(); // Should be removed
        expect(tree.lookup(5)).toEqual(expect.objectContaining({ value: 5 })); // Should still exist
    });

    it('should return false when removing a non-existent node', () => {
        tree.insert(10);
        expect(tree.remove(20)).toBeFalsy(); // Node does not exist
    });

    it('should handle removing the only node in the tree', () => {
        tree.insert(10);
        expect(tree.remove(10)).toBeTruthy(); // Remove the only node
        expect(tree.lookup(10)).toBeFalsy(); // Should be removed
    });

    it('should handle removing a node that is the left child of its parent', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.remove(5)).toBeTruthy(); // Remove left child
        expect(tree.lookup(5)).toBeFalsy(); // Should be removed
        expect(tree.lookup(10)).toEqual(expect.objectContaining({ value: 10 })); // Should still exist
        expect(tree.lookup(15)).toEqual(expect.objectContaining({ value: 15 })); // Should still exist
    });

    it('should handle removing a node that is the right child of its parent', () => {
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        expect(tree.remove(15)).toBeTruthy(); // Remove right child
        expect(tree.lookup(15)).toBeFalsy(); // Should be removed
        expect(tree.lookup(10)).toEqual(expect.objectContaining({ value: 10 })); // Should still exist
        expect(tree.lookup(5)).toEqual(expect.objectContaining({ value: 5 })); // Should still exist
    });
});