Binary Search Tree Questions

Hello, I have questions on binary search tree questions. Below are the instructions and attached are the files associated with the questions. This should be an easy assignment.

——

QUESTION 1

Show the binary search tree built by adding the following numbers in this specific order, assuming the tree is empty to start with: 30, 63, 2, 89, 16, 24, 19, 52, 27, 9, 4, 45 (You may need to add more boxes to the diagram).

QUESTION 2

The trouble with binary search trees is that they can become unbalanced depending on the order in which you insert values. Give an order for inserting the letters P, A, I, F, W, Q, N, X, E, C, G, S, B, Z such that your intermediate trees as well as the resulting tree are complete binary search trees. Please provide the resulting binary search tree along with the order. (Hint: it might be helpful to first draw the full/complete tree to figure out how the values must be arranged, then you can determine the order in which to insert them.)

QUESTION 3

• Part A: Given the following tree, show the tree after removing the value 40:question3.pdf
• Part B: Using the tree produced by Part A, show the tree after removing the value 50.
  

  QUESTION 4

  The computer has built the following decision tree for the Guess the Animal Game:question4.pdf

• The player has an animal in mind and will answer the questions shown in the tree. Each of the player’s responses is used to determine the next question to ask. For example, if the player is thinking of a sea turtle, she would answer Yes to the first (top) question, “does it live in the water?”, which leads to the second question “is it a mammal?”, to which she would answer No.Show the decision tree that the computer should build after adding a Zergling and a question to differentiate it, “Does it eat space marines?”, to the tree. The question and the animal should be added below existing questions in the tree. Note that this instruction says that you should keep the existing questions in the tree intact and then add the new animal and new question. It doesn’t restrict changing the existing nodes that contain animals. You can definitely make changes to such nodes. Finally, note that Zerglings do eat space marines, do not live in the water, and do not climb trees.