Use the tree in Figure 1 for exercises 1, 2, 5, 6, 7, and 8.

Figure 1

1. What node or nodes are

a. The trees root?

b. Parents

c. Children of the parents in part b?

d. Siblings?

e. Ancestors of 50?

f. Descendants of 20?

g. Leaves?

2. What is the height of the tree?

3. Write preconditions and postconditions for the ADT binary search three operations (the methods declared in the interface template for the ADT binary tree (see Chapter 15 ListingCode.html).

4. Consider a method isLeaf that returns true if a binary tree is a one-node treethat is, if it consists of only a leafand returns false otherwise.

a. Specify the method isLeaf (write the specifications of the method isLeaf).

b. Is isLeaf were not a method of a class of binary trees, would a client of the class be able to implement isLeaf? Explain

5. Starting with an empty binary search tree, in what order should you insert items to get the binary search tree in Figure 1.

6. Using the binary tree in Figure 1, trace the search algorithm when it searches for

a. 30

b. 15

7. Consider the binary search tree in Figure 1. What tree results after you inset the nodes 80, 65, 75, 45, 35, and 25, in that order?

8. Suppose that you traverse the binary search tree in Figure 1 and write the data item in each node visited to a file. You plan to read this file later and create a new binary search tree by using the ADT binary search tree operation add. In creating the file, in what order should you traverse the tree so that the new tree will have exactly the same shape and nodes as the original tree?

Use the tree in Figure 2 for exercises 9 and 10

Figure 2

9. What are the preorder, inorder, and postorder traversals of the binary tree in Figure 2?

10. Is the tree in Figure 2 a binary search tree? Explain.

11. Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the order given?

a. W, T, N, J, E, B, A

b. W, T, N, A, B, E, J

c. A, B, W, J, N, T , E

d. B, T, E, A, N, W, J