# Tests for Assn 2: BST

General Notes:

We perform an in-order traversal on your tree to avoid issues of people handling remove differently. So long as an in-order traversal succeeds we consider your tree correct. Also note that in the trees for remove tests there are lowercase letters. Those indicate the ones we removed from the tree.

You should also test yourself!! Don't use what we give you as an excuse not to self-test!!

Test Cases
```General Notes: We perform an in-order traversal on your list to avoid issues of people handling
remove differently. So long as an in-order traversal succeeds we consider your tree correct
Also note that in the trees for remove tests there are lowercase letters. Those indicate the
ones we removed from the tree.

You should also test yourself!! Don't use what we give you as an excuse not to self-test!!

Size:
Case 0: size() == 0;
Case 1: insert(a), insert(b), size() == 2
Case 2: insert(a), insert(b), remove(a), size() == 1

Insert:
Case 0(Line): insert(C), insert(B), insert(A), in-order == (A, B, C)
C
/
B
/
A
Case 1(left-insert): insert(B), insert(A), insert(D), insert(C), in-order = (A, B, C, D)
B
/ \
A D
/
C
Case 2(right-insert): insert(B), insert(A), insert(D), insert(C), insert(E), in-order = (A, B, C, D, E)
B
/ \
A D
/ \
C   E

Remove: {The removed node is marked as lower-case in graph}
Case 0: insert(A), insert(B), remove(B), in-order = (A)
A
\
b
Case 1(root): insert(B), insert(A), insert(C), remove(A), in-order = (B, C)
Case 2(nonroot internal node): insert(B), insert(A), insert(D), insert(C), insert(E), remove(D) in-order = (A, B, C, E)
B
/ \
A d
/ \
C   E
Case 3(leaf): insert(B), insert(A), insert(D), insert(C), insert(E), remove(E) in-order = (A, B, C, D)
B
/ \
A D
/ \
C   e
Case 4(complex internal 0): insert(0), insert(C), insert(A), insert(B), remove(C) in-order = (0, A, B)
0
\
\
c
/
/
A
\
B
Case 5(complex internal 1): insert(0), insert(C), insert(E), insert(D), remove(C) in-order = (0, D, E)
0
\
\
c
\
\
E
/
D
Case 6(complex internal 2): insert(0), insert(C), insert(A), insert(B), insert(E), insert(D), remove(C) in-order = (0, A, B, D, E)
0
\
\
c
/ \
/   \
A     E
\   /
B D

Case 7(Multiple remove): insert(0), insert(C), insert(A), insert(B), insert(E), insert(D), remove(C), remove(A), remove(D), remove(B), remove(E), in-order = (0)
0
\
\
c
/ \
/   \
a     E
\   /
b d

Insert After Remove:
Case 0(root): insert(A), remove(A), insert(B), in-order = (B)
Case 1(left): insert(D), insert(B), remove(B), insert(B), insert(E), in-order = (B, D, E)
Case 2(internal): insert(B), insert(A), insert(D), insert(C), insert(E), remove(E), insert(F), insert(E) in-order = (A, B, C, D, E, F)

findMin & findMax:
(The difference between findMax and findMin will give in message)
Case 0(One element): insert(A), findMax() == A, findMin() = A
Case 1(Two elements): insert(A), insert(B), findMax() == B, findMin() == A
Case 2(remove): insert(A), insert(C), insert(B), remove(C), findMax() == B, findMin() == A

empty:
Case 0: new BST, empty() = true
Case 1: insert(B), insert(A), insert(D), insert(C), insert(E), remove(B), remove(A), remove(D), remove(C), remove(E),empty() == true
B
/ \
A D
/ \
C   E

contains:
Case 0: insert(B), insert(A), insert(D), insert(C), insert(E), contains(D) == True
B
/ \
A D
/ \
C   E
Case 1: insert(B), insert(A), insert(D), insert(C), insert(E), remove(D), contains(D) == False, contains(C) = True, contains(E) = True
B
/ \
A d
/ \
C   E

height:
Case0: insert(B), insert(A), insert(D), insert(C), insert(F), insert(E), height()==3

```