Consider an array$-$based implementation of a binary search tree. Figure $16-1$ presents such a

representation for a particular binary search tree.

FIGURE $16-1($a$)$ A binary tree of names; $($b$)$ its implementation using the array tree

a$)$ 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.

$["$Alan$",$ "Bob", "Doug", "Elra", "Elea", "Jane", "Nancy", "Tom", "Tom", "Wendy"$]$

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

exercise.

$bst.$add$(Doug)$; $[\text{'}AlanBobDougEleaNancyTomWendy]$

$bst.$add$(Nancy)$;rarr$[AlanBobDougElea\text{'}TomWendy]$

$bst.$add$(Bob)$;rarr$[\text{'},$ Alan, 'DougElea'TomWendy$]$

$bst.$add$(Sarah)$;rarr$[\text{'},$ Alan, Doug, Sarah, Elea, $\text{'},$ Tom, Wendy$]$

The first operation adds "Doug" to the tree, the second and third remove "Nancy" and

"Bob," and the fourth adds "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.