The motivation behind this problem is to practice implementing binary trees and

understand how stacks are used by compilers to implement recursion. You will be

writing a sorting algorithm. You will first insert all the integer keys to be sorted into an

initially empty binary search tree T, and then traverse T to retrieve the keys in sorted

order. But instead of implementing the traversal recursively, you will use a stack.

a. You can use your stack implementation from the previous assignment but you

may need to update the type stored. You are also allowed to use Javas Stack.

b. Implement a binary search tree class. Each node in your implementation should

have fields for a key and left and right subtrees but should not have a parent

reference. The methods in the BST include

i. Return the key at the root

ii. Return the left subtree of the root

iii. Return the right subtree of the root

iv. Test if the tree is empty

v. Construct an empty tree

vi. Test if the tree contains a given value vii. Insert a new Integer into the BST 1. In the Weiss book there is an example insertion method.

Your method will be similar but you must support duplicate values.

/*

Internal method to insert into a subtree.

@param x the item to insert.

@program t the node that roots the subtree.

@return the new root of the subtree.

*/

Private BinaryNode insert(AntType x, BinaryNode<>AnyType)

{

If ( t== null)

Return new BinaryNode<> ( x, null, null);

int compareResult = x.compareTo ( t.element );

if ( CompareResult < 0 )

t.left = insert ( x, t.left );

else if ( compareREsult > 0 )

t.right = inser ( x, t.right );

else

; // Duplicate, do nothing

return t;

}

c. What type of tree traversal do you need to implement to retrieve the keys from

your binary search tree in sorted order? Implement it without recursion, instead

using your stack to simulate the recursion.

i. Hints: What type of object needs to be stored on the stack? Exactly which

object needs to be pushed when you are about to start the traversal of

the left subtree? When do you pop the stack and what do you do with

the result that is popped? What do you do when the stack is empty?

d. Implement a class called SortIntegers. Include a method called

sortIntegerArray which will take as an argument an array of Integers, it will

then insert them into the binary search tree class you implemented above, then

use the tree traversal method you implemented in part c to sort the integers.

Return an array of the Integers sorted.

e. You are not required to turn in any testing methods.