1. Given the BST tree below, fill in the values in the table.
Figure: see image.
| Property | Value |
| Height of tree | |
| Height of node 45 | |
| Depth of node 17 | |
| Node 76 degree | |
| Tree degree | |
| Name the nodes in left subtree of node 98 | |
| Order of tree | |
| Internal path length | |
| External path length |
2. Perform the traversals for the above tree:
a) reverse post order: ____________________
b) preorder traversal: ____________________
c) Give the array representation of the binary tree in #1.
3. Draw the BST that is created if the following numbers are inserted into an initially empty BST in the given order. Then show the 2 possible trees after deleting the root.
56, 77, 33, 26, 17, 25, 88, 45, 90, 83
4. Insert the following letters into an empty B-tree of order 5 in the order given:
P G E V T D L A H B I Y O S N F
5. a) Add the elements 77, 54, 21, 79, 92, 3, 46, 17, 26, 18, 31 into a binary min heap in this order.
b) Show the resulting binary min heap after removing the root from the min heap in #5a.
6. Draw the binary expression trees for the following:
a) 5 / (17 + 49) + 6 * 4 + 3 * (13 % 15 - 12)
b) t / (e * r + d % f ^ v - a)
7. Trace the construction of an AVL tree using the insertion sequence:
57, 15, 80, 32, 17, 45, 25, 61, 48, 15
8. Given the following 2-3 tree, show clearly each value that is deleted.
Delete the values in the following sequence: 56, 87, 12, 71, 33
Figure: see image.
9. Insert the following values into an initially empty Red-Black tree in the order given.
Insert: 93, 85, 24, 13, 47, 59, 18, 36, 14, 35, 77, 63 Also, answer the questions below.
What is the black-height of node 59?
What is the height of node 24?
10. Build a Huffman Encoding tree using the following character frequencies. Also, fill in the codeword for each digit.
| Digit | Frequency | Digit | CODEWORD |
| 0 | 12 | 0 | |
| 1 | 10 | 1 | |
| 2 | 16 | 2 | |
| 3 | 7 | 3 | |
| 4 | 9 | 4 | |
| 5 | 2 | 5 | |
| 6 | 5 | 6 | |
| 7 | 1 | 7 | |
| 8 | 4 | 8 | |
| 9 | 2 | 9 |