Array-based Implementation of a Binary Search Tree

Consider an array-based implementation of a binary search tree bst . Figure 16-1 presents such a representation for a particular binary search tree.

1. Depict the array in an array-based implementation for the binary search tree in Figure 15-14 a of

Chapter 15 . Assume that tree items are strings.

1. Show the effect of each of the following sequential operations on the array in parta of this exercise.

bst.add(“Doug”);

bst.add(“Nancy”);

bst.add(“Bob”);

bst.add(“Sarah”);

1. Repeat partsa and b of this exercise for the tree in Figure 15-14 b.
2. Write an inorder traversal algorithm for this array-based implementation.