a. Depict the array in an array-based implementation for the binary search tree in Figure 15-14 a. Assume that tree items are strings.

b. Show the effect of each of the following sequential operations on the array in part a of this exercise.

bst.add("Doug");

bst.add("Nancy");

bst.add("Bob");

bst.add("Sarah");

c. Repeat parts a and b of this exercise for the tree in Figure 15-14 b. d. Write an inorder traversal algorithm for this array-based implementation.

d. Write an inorder traversal algorithm for this array-based implementation.

 

Many different binary search trees can contain the same data, however. For example, in addition to the tree in Figure 15-13, each tree in Figure 15-14 is a valid binary search tree for the names Alan, Bob, Elisa, Jane, Nancy, Tom, and Wendy. Although these trees have different shapes, each one satis- fies the requirements of a binary search tree. FIGURE 15-14 Binary search trees with the same data as in Figure 15-13 (b) Alan Bob (a) Jane Elisa Nancy Alan O O Tom Bob Elisa Wendy 20000 Jane Nancy Alan Bob Jane Elisa Several different binary search trees are possible for the same data 0 Tom Nancy Wendy