## CS 2401 Test #3

Date: Thursday, April 29, 2010.

Name: ___________________________________________________________________

1-2. Show, step by step, what will happen if we add elements 4, 29, 10, 24, 1, and 3 to the binary search tree; do not forget to balance at every step at which balancing is necessary. No code is needed.

```

```
3. Redraw the binary search tree below showing how it will look like after the elements 75 and 30 are deleted. Assume that no tree balancing takes effect after the elements 75 and 30 are deleted.
```                          60
/     \
/       \
/         \
30           90
/    \       /    \
15      45    75     105
/  \    /  \  /  \   /   \
10  20  40 55 70  85 100  110

```
4. Consider a method printBinaryTree() that traverses and prints the contents of binary trees.
```                         60
/     \
/       \
/         \
30           90
/    \       /    \
15      45    75     105
/       /  \  /  \      \
10     40 55  70  85      110
```
• Show the output of printBinaryTree() for the binary tree above assuming that the method uses a preorder traversal and it prints the key of a node at the time the node is visited.
• Show the output of printNinaryTree() for the binary tree above assuming that the method uses a postorder traversal and it prints the key of a node at the time the node is visited.
• Show the output of printNinaryTree() for the binary tree above assuming that the method uses a inorder traversal and it prints the key of a node at the time the node is visited.

```

```
5. Show, step by step, how binary search will look for an element 20 in the sorted list 1, 3, 4, 10, 20, 29. No code is needed. What is the worst-case and average complexity of binary search?

```

```
6. Show, step by step, how bubble sort will sort a list 4, 29, 10, 24, 1, 3. No code is needed. What is the worst-case and average complexity of bubble sort?

```

```
7. Show, step by step, how selection sort will sort a list 4, 29, 10, 24, 1, 3. No code is needed. What is the worst-case and average complexity of selection sort?

```

```
8. Show, step by step, how insertion sort will sort a list 4, 29, 10, 24, 1, 3. No code is needed. What is the worst-case and average complexity of insertion sort?

```

```
9. Show, step by step, how quicksort will sort a list 4, 29, 10, 24, 1, 3. No code is needed. What is the worst-case and average complexity of quicksort?

```

```
10. Show, step by step, how mergesort will sort a list 4, 29, 10, 24, 1, 3. No code is needed. What is the worst-case and average complexity of mergesort?