This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them.

You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below

Your code should have a menu driven user interface at the command line with the following options:

>> Enter choice [1-7] from menu below:

Insert node (prompts the user to enter node value and then inserts it into the BST)

Print tree (in-order) (You can reuse the code on page 164, Fig. 4.59 of the text) -code is provided below

Print number of leaves in tree (subpart a)

Print the number of nodes in T that contain only one child (subpart b)

Print the number of nodes in T that contain only two children (subpart c)

Print the level order traversal of the tree (subpart d)

Exit program

Your program should not exit until 7) is selected. Use this tree interface for the following subparts of this question:

Write methods in Java for each of the following operations. You can put the codes for each subpart in the same Java program, under different methods.

numLeaves method that returns the number of leaves in T (2 points)

numOneChildNodes method that returns the number of nodes in T that contain only one child (2 points)

numTwoChildrenNodes method that returns the number of nodes in T that contain only two children (2 points)

levelOrder method that prints the level order traversal of the tree. A level order traversal first lists the root, then nodes at depth 1, followed by nodes at depth 2 and so on. (20 points)

An example of level-order traversal is given below:

Level order traversal: 8 3 10 1 6 14 4 7 13

You can print your output on a single line, like, 8 3 10 1 6 14 4 7 13

__________________________________________________________________________________________________________________________

//insert method

private AvlNode insert( AnyType x, AvlNode t )

{

if( t == null )

return new AvlNode<>( x, null, null );

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

if( compareResult < 0 )

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

else if( compareResult > 0 )

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

else

; // Duplicate; do nothing

return balance( t );

}

// print tree method

public void printTree( )

{

if( isEmpty( ) )

System.out.println( "Empty tree" );

else

printTree( root );

}

/* Internal method to print a subtree in sorted order. @param t the node that roots the subtree. */

private void printTree( BinaryNode t )

{

if( t != null )

{

printTree( t.left );

System.out.println( t.element );

printTree( t.right );

}

}