1 | module datatypes |
2 | |
3 | // Make an insert of one element and check if |
4 | // the bst is able to fin it. |
5 | fn test_insert_into_bst_one() { |
6 | mut bst := BSTree[int]{} |
7 | assert bst.insert(10) == true |
8 | assert bst.contains(10) == true |
9 | assert bst.contains(20) == false |
10 | } |
11 | |
12 | // Make the insert of more element inside the BST |
13 | // and check if the BST is able to find all the values |
14 | fn test_insert_into_bst_two() { |
15 | mut bst := BSTree[int]{} |
16 | assert bst.insert(10) |
17 | assert bst.insert(20) |
18 | assert bst.insert(9) |
19 | |
20 | assert bst.contains(9) |
21 | assert bst.contains(10) |
22 | assert bst.contains(20) |
23 | assert bst.contains(11) == false |
24 | } |
25 | |
26 | // Test if the in_order_traversals list return the correct |
27 | // result array |
28 | fn test_in_order_bst_visit_one() { |
29 | mut bst := BSTree[int]{} |
30 | assert bst.insert(10) |
31 | assert bst.insert(20) |
32 | assert bst.insert(21) |
33 | assert bst.insert(1) |
34 | |
35 | assert bst.in_order_traversal() == [1, 10, 20, 21] |
36 | } |
37 | |
38 | // Test if the post_order_bst_visit return the correct |
39 | // result array |
40 | fn test_post_order_bst_visit_one() { |
41 | mut bst := BSTree[int]{} |
42 | assert bst.insert(10) |
43 | assert bst.insert(20) |
44 | assert bst.insert(21) |
45 | assert bst.insert(1) |
46 | |
47 | assert bst.post_order_traversal() == [1, 21, 20, 10] |
48 | } |
49 | |
50 | // Test if the pre_order_traversal return the correct result array |
51 | fn test_pre_order_bst_visit_one() { |
52 | mut bst := BSTree[int]{} |
53 | assert bst.insert(10) |
54 | assert bst.insert(20) |
55 | assert bst.insert(21) |
56 | assert bst.insert(1) |
57 | |
58 | assert bst.pre_order_traversal() == [10, 1, 20, 21] |
59 | } |
60 | |
61 | // After many insert check if we are abe to get the correct |
62 | // right and left value of the root. |
63 | fn test_get_left_root() { |
64 | mut bst := BSTree[int]{} |
65 | assert bst.insert(10) |
66 | assert bst.insert(20) |
67 | assert bst.insert(21) |
68 | assert bst.insert(1) |
69 | |
70 | left_val := bst.to_left(10) or { -1 } |
71 | assert left_val == 1 |
72 | |
73 | right_val := bst.to_right(10) or { -1 } |
74 | assert right_val == 20 |
75 | } |
76 | |
77 | // Check if BST panic if we call some operation on an empty BST. |
78 | fn test_get_left_on_empty_bst() { |
79 | mut bst := BSTree[int]{} |
80 | |
81 | left_val := bst.to_left(10) or { -1 } |
82 | assert left_val == -1 |
83 | |
84 | right_val := bst.to_right(10) or { -1 } |
85 | assert right_val == -1 |
86 | } |
87 | |
88 | // Check the remove operation if it is able to remove |
89 | // all elements required, and mantains the BST propriety. |
90 | fn test_remove_from_bst_one() { |
91 | mut bst := BSTree[int]{} |
92 | assert bst.insert(10) |
93 | assert bst.insert(20) |
94 | assert bst.insert(21) |
95 | assert bst.insert(1) |
96 | assert bst.in_order_traversal() == [1, 10, 20, 21] |
97 | assert bst.remove(21) |
98 | |
99 | assert bst.in_order_traversal() == [1, 10, 20] |
100 | } |
101 | |
102 | // Another test n the remove BST, this remove an intermidia node |
103 | // that it is a triky operation. |
104 | fn test_remove_from_bst_two() { |
105 | mut bst := BSTree[int]{} |
106 | assert bst.insert(10) |
107 | assert bst.insert(20) |
108 | assert bst.insert(21) |
109 | assert bst.insert(1) |
110 | assert bst.in_order_traversal() == [1, 10, 20, 21] |
111 | assert bst.remove(20) |
112 | |
113 | assert bst.in_order_traversal() == [1, 10, 21] |
114 | } |
115 | |
116 | // check if we are able to get the max from the BST. |
117 | fn test_get_max_in_bst() { |
118 | mut bst := BSTree[int]{} |
119 | assert (bst.max() or { -1 }) == -1 |
120 | assert bst.insert(10) |
121 | assert bst.insert(20) |
122 | assert bst.insert(21) |
123 | assert bst.insert(1) |
124 | max := bst.max() or { -1 } |
125 | assert max == 21 |
126 | } |
127 | |
128 | // check if we are able to get the min from the BST. |
129 | fn test_get_min_in_bst() { |
130 | mut bst := BSTree[int]{} |
131 | assert (bst.min() or { -1 }) == -1 |
132 | assert bst.insert(10) |
133 | assert bst.insert(20) |
134 | assert bst.insert(21) |
135 | assert bst.insert(1) |
136 | min := bst.min() or { -1 } |
137 | assert min == 1 |
138 | } |