1. Describe the differences between our specifications of the Sorted List ADT an
ID: 3539471 • Letter: 1
Question
1. Describe the differences between our specifications of the Sorted List ADT and the Binary Search Tree ADT.
The Sorted List ADT and the Binary Search Tree ADT have very similar specifications (interfaces) but there are a few notable differences. Firstly, ListInterface (Sorted List ADT) has only one method of iteration. The BSTInterface (Binary Search Tree) specifies three methods of iteration, inorder, preorder, and postorder. Thus the reset and getNext methods in BSTInterface take a parameter that specifies the interation type whereas these methods take no parameters in ListInterface. BSTInterface contains isEmpty but ListInterface does not. This is due to the fact that ListInterface has reference based and array based implementations but BSTInterface only has a referenced based implementation (although an array based implementation can be engineered for the binary search tree). Since isEmpty is implemented in the reference based implementation but not in the array based implementations it cannot be included in the interface. Finally, ListInterface contains a toString method but BSTInterface does not. Since the idea of outputting an entire binary search tree as a formatted string is not even broached, there is no need for it in the interface.
Explanation / Answer
1.Sorted List ADT has only one method of iteration but Binary Search Tree ADT specifies three methods of iteration, inorder, preorder, and postorder.
2.The reset and getNext methods in BSTInterface take a parameter that specifies the interation type whereas these methods take no parameters in ListInterface.
3. BSTInterface contains isEmpty but ListInterface does not. This is due to the fact that ListInterface has reference based and array based implementations but BSTInterface only has a referenced based implementation (although an array based implementation can be engineered for the binary search tree). Since isEmpty is implemented in the reference based implementation but not in the array based implementations it cannot be included in the interface.
4. ListInterface contains a toString method but BSTInterface does not. Since the idea of outputting an entire binary search tree as a formatted string is not even broached, there is no need for it in the interface.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.