Assume we have an IntBST class, which implements a binary search tree of integers. The field of the class is a Node variable called root that refers to the root element of the tree.
1) Write a recursive method for this class that computes and returns the sum of all integers less than the root element. Assume the tree is not empty and there is at least one element less than the root.
2) Write a recursive method that prints all of the leaves, and only the leaves, of a binary search tree.
3) Write a method, using recursion or a loop, that returns the smallest element in the tree.
Partition the array given below. Assume the first element is chosen as the pivot element. Draw the partitioned array and clearly identify the left and right partitions. Be careful: You are partitioning the array, not sorting the array.
|
13 |
92 |
11 |
56 |
9 |
15 |
81 |
3 |
10 |
22 |
63 |
9 |
46 |
5 |
4 |
2) Next, partition the right partition, again choosing the first element as the pivot.
3) Identify two methods of choosing a pivot when partitioning an array. Clearly explain how the choice of pivot affects the performance of the Quick Sort algorithm.
1) Add the following integers to a binary search tree. Draw the resulting tree.
33 1 85 30 57 40 45 19 97 25 6
2) The resulting tree should not be an AVL Tree. Identify all unbalanced nodes in the tree and explain why each is unbalanced.
3) How many of the numbers above can you add to a binary search tree before the tree becomes unbalanced? Draw the AVL tree containing only those numbers.
0 comments