1. Begin with the following binary search tree, draw the BST that results after the operation or sequence of operations is performed. (All questions are independent and each question starts from the BST as following) see image.
a. How many leaves are in the tree?
b. What is the height of node 38? What is the depth of 54? What is the height of the tree?
c. Insert 20, 10, 65, 42, and 94
d. Delete 48, 75, and 22 (based on the original figure, NOT on c).
e. Insert 45, delete 48, insert 59, delete 75, insert 94, delete 91 (based on the original figure, NOT on d).
2. For the infix arithmetic expressions below, draw a binary tree that represents the expression, and then use tree traversals to find the equivalent prefix and postfix expressions.
a. (A-B)-(C+D)
b. (A/ B)-(((C-D)-E)-F)
c. ((A*B*C)-(D-E*F))/((G-H)*(I+J))
3. Construct the Huffman tree and show the encoding for the some words and weights given in the following table.
| Words | Weight |
| a | 5,000 |
| b | 2,000 |
| c | 10,000 |
| d | 8,000 |
| e | 22,000 |
| f | 49,000 |
| g | 4,000 |
8.1 Start with the tree.java program (Listing 8.1) and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children. Don't worry if the tree is unbalanced. Note that this will not be a search tree; theres no quick way to find a given node. You may end up with something like this: see image.
8.2 Expand the program in Programming Project 8.1 to create a balanced tree. One way to do this is to make sure that as many leaves as possible appear in the bottom row. You can start by making a three-node tree out of each pair of one- node trees, making a new + node for the root. This results in a forest of three- node trees. Then combine each pair of three-node trees to make a forest of seven-node trees. As the number of nodes per tree grows, the number of trees shrinks, until finally there is only one tree left.