File Lab3BST.java contains a nearly-complete program that constructs a number of binary trees and then tests each to see if the values in the tree were inserted in binary search tree order.

In these trees, no duplicate values are permitted, so binary search tree order can be written as follows: the value at each node n must satisfy

values in the left subtree of n < value at n < values in the right subtree of n,

where the left/right subtree of n is the left/right child of n and all of that childs descendants.

You must write the following methods:

getMax: A recursive method in the Node class with NO parameters that returns the maximum value stored in the subtree that consists of this and all the descendants of this. The method should assume that the tree is a binary search tree (i.e., that the values in the tree satisfy the binary search tree property). The method should simply use recursion to move to the right child (if there is one) returning the value of this if it has no right child, otherwise returning whatever the recursive call returns.

getMin: A recursive method in the Node class with NO parameters that returns the minimum value stored in the subtree that consists of this and all the descendants of this. The method should assume that the tree is a binary search tree (i.e., that the values in the tree satisfy the binary search tree property). The method should simply use recursion to move to the left child (if there is one) returning the value of this if it has no left child, otherwise returning whatever the recursive call returns.

isOrdered(): A driver method in the BinaryTree class with NO parameters that returns a boolean value. It returns true if the calling tree is in BST order, and false otherwise. It simply handles the case when the tree is empty; otherwise it calls a Node method, also called isOrdered() (see next method), on the root of the tree and returns whatever the Node method returns to it.

isOrdered(): A recursive method in the Node class that does most of the work of deciding whether a non-empty tree is ordered or not. It should have NO parameters and return a boolean value. It should return true only if

The left child is in BST order (if there is a left child), AND

The data in this is greater than the maximum value in the left child (if there is one), AND

The right child is in BST order (if there is a right child), AND

The data in this is less than the minimum value in the right child (if there is one).

Otherwise, the method should return false.

This method should do its job in a traversal (since it has to visit every Node to be sure that the tree is in BST order).

Just add the bodies of the BinaryTree and Node class isOrdered methods and the Node class methods getMax and getMin, and change nothing else in the Lab3BST.java file.

Lab3BST.java :

/************************************************************************* * * Lab3 (Part 2) - creates a number of binary trees, randomly choosing * (1) whether to insert value in binary search tree (BST) * order or not, * (2) the size of the tree (up to MAX_TREE_SIZE), and * (3) the values to insert. * It ensures that the tree has exactly the chosen number * of distinct values (i.e., no duplicates are allowed). * * It prints out the tree after the tree is created using * an inorder traversal, so you can _see_ whether the tree * is in BST order or not. * * Then it uses a student-written method to test whether * the tree is in BST order or not, printing out the * result returned by the student-written method. * ***************************************************************************/

import java.util.*;

public class Lab3BST {

/********************************************************************* * * Global constants * **********************************************************************/ private final static int NUM_TREES = 10; // number of trees to create private final static int MAX_TREE_SIZE = 30; // max number of values in a tree private final static int MAX_NODE_VALUE = 100; // max key value to be inserted into a tree.

/********************************************************************* * * Global variable * **********************************************************************/ private static Random generator = new Random(System.nanoTime()); // so only ONE random number generator is created (for efficiency)

/********************************************************************* * * main * **********************************************************************/ public static void main( String[] args ) { BinaryTree tree; boolean ordered; int treeSize; // number (distinct) values to put in the tree int insertedCount; // number of (distinct) values inserted into the tree so far int value; // random value to try inserting in the tree

// Print out titles

System.out.println( " COMP 2140 Lab 3 - Part 2: Testing If Binary Trees are BST Ordered " + "-------------------------------------------------------- " );

System.out.println( "Note: When a BST is printed out in an inorder traversal, the values will be in sorted order." );

// Construct NUM_TREES different trees, // some ordered and some not, and test // the isOrdered method on them.

for ( int i = 0; i < NUM_TREES; i++ ) { tree = new BinaryTree();

// Flip a coin to decide if insertions should be // done in BST order or randomly in this tree. ordered = generator.nextInt( 2 ) == 0;

// Get a random (non-zero) tree size for this tree. treeSize = 1 + generator.nextInt( MAX_TREE_SIZE );

// Keep trying to insert random values until // treeSize distinct values have been inserted. insertedCount = 0; while ( insertedCount < treeSize ) { value = generator.nextInt( MAX_NODE_VALUE ); if ( ordered ) // try to insert in BST order { if ( tree.insert( value ) ) { insertedCount++; } } else // insert, moving randomly left or right // IF the value was not already inserted // randomly somewhere in the tree if ( !tree.somewhereInTheTree( value ) ) { tree.insertRandomly( value ); insertedCount++; }

} // end while insertedCount < treeSize

// Print out the tree just created System.out.println( " ---------------- Tree number " + i + " with " + treeSize + " values printed by an inorder traversal: " ); tree.printTree(); if ( ordered ) System.out.println( "Values were inserted using a correct BST insertion method." ); else System.out.println( "Values were NOT inserted in BST order (just inserted in random places in the tree)." );

// Use isOrdered() to see if the tree is in BST order System.out.print( " Your isOrdered() method says that the tree " ); if ( tree.isOrdered() ) System.out.print( "IS" ); else System.out.print( "is NOT" ); System.out.println( " in BST order." );

} // end for i < NUM_TREES

// Print out a closing method

System.out.println( " --------------------- Lab 3 part 2 ended normally. " ); } // end main

} // end class Lab3BST

/************************************************************************* * * BinaryTree * * - A binary tree, which could either have values randomly placed in it, * OR could have values inserted in binary search tree (BST) order. * *************************************************************************/

class BinaryTree {

/********************************************************************* * * Instance variable * **********************************************************************/ private Node root; // A pointer to the root (if the tree's not empty)

/********************************************************************* * * Constructor * **********************************************************************/ public BinaryTree() // constructs an empty binary tree { root = null; }

/********************************************************************** * insert * * Insert a value (key) in binary search tree order. * * (A "driver" method that handles the special case * when the tree is empty, and otherwise calls a * Node method called "insertBelow" to do the work.) * **********************************************************************/ public boolean insert( int key ) { boolean inserted = false;

if ( root == null ) { root = new Node( key ); inserted = true; } else inserted = root.insertBelow( key );

return inserted; }

/********************************************************************** * insertRandomly * * Insert a value (key) in a new leaf in a random place in the tree. * * (A "driver" method that handles the special case * when the tree is empty, and otherwise calls a * Node method called "insertRandomlyBelow" to do the work.) * **********************************************************************/ public void insertRandomly( int key ) { if ( root == null ) root = new Node( key ); else root.insertRandomlyBelow( key ); }

/********************************************************************** * somewhereInTheTree * * A search method for a random (non-binary-search-tree) binary tree. * * (A "driver" method that handles the special case when the * tree is empty, and otherwise calls a Node method called * "somewhereInTheTree" to do the work.) * **********************************************************************/ public boolean somewhereInTheTree( int key ) { boolean result = false;

if ( root != null ) result = root.somewhereInTheTree( key );

return result; }

/********************************************************************** * printTree * * A print method to print a tree in an inorder traversal * * (A "driver" method that handles the special case when the * tree is empty, and otherwise calls a Node method called * "printTree" to do the work.) * **********************************************************************/ public void printTree() { if ( root == null ) System.out.print( "The tree is empty!" ); else root.printTree(); System.out.println(); }

/********************************************************************* * * isOrdered * * Tests whether a binary tree is in BST order or not * (returns true if it is, and false if it isn't). * * * This public driver method handles the special case when the * tree is empty, and otherwise calls a recursive helper method * in the Node class (also called "isOrdered") to do the work. * **********************************************************************/ public boolean isOrdered() { //===============> YOUR CODE GOES HERE <=============== }

} // end class BST

/************************************************************************* * Node * * - a Node in a BinaryTree * - the data stored in a Node is a single int * *************************************************************************/ class Node {

/********************************************************************* * * Global variable shared by all Nodes * **********************************************************************/ private static Random generator = new Random(System.nanoTime()); // so only ONE random number generator is created (for efficiency)

/********************************************************************* * * Instance variables * **********************************************************************/ private int data; private Node left; // pointer to the left child of the Node private Node right; // pointer to the right child of the Node

/********************************************************************* * * Constructors * **********************************************************************/ public Node( int d, Node l, Node r ) { data = d; left = l; right = r; }

public Node( int d ) { this( d, null, null ); }

/********************************************************* * somewhereInTheTree * * Decide whether key is in this or any of its descendants * by doing a pre-order traversal of the tree rooted at this. * (Used when the tree is not in BST order to see if a * random value is already present in the tree or not, so * we can avoid inserting duplicates.) * * Returns true if key is in the tree and false otherwise. * * Makes use of the lazy evaluation of || (OR) and && (AND) * to stop looking any further if it finds key somewhere. **********************************************************/ public boolean somewhereInTheTree( int key ) { return ( data == key ) || ( ( left != null ) && left.somewhereInTheTree( key ) ) || ( ( right != null ) && right.somewhereInTheTree( key ) ); }

/********************************************************* * insertBelow * * Insert the key either as a child of this (if this has * no left/right child) as appropriate to maintain BST order * OR make a recursive call to insert key further down the tree * (under the appropriate child of this). * * Returns true if key is successfully inserted and false if * the key is a duplicate (and is therefore not inserted). **********************************************************/ public boolean insertBelow( int key ) { boolean inserted = false; // Assume key is a duplicate (not inserted)

if ( key < data ) // key should be a descendant to the left of this { if ( left != null ) // this already has a left child inserted = left.insertBelow( key ); else // this doesn't have a left child, so insert here! { left = new Node( key ); inserted = true; } } else if ( data < key ) // key should be a descendant to the right of this { if ( right != null )// this already has a right child inserted = right.insertBelow( key ); else// this doesn't have a right child, so insert here! { right = new Node( key ); inserted = true; } } // else if key == data, we're already set to return false return inserted; } // end insertBelow

/********************************************************* * Insert the key in a leaf randomly placed in the tree. * * Choose to go left or right randomly until we find * no child in the chosen direction, where we insert the new * leaf. * * Assumption: The key is NOT in the tree (i.e., we've already * searched the tree and not found the key * Doesn't return anything, because it always inserts. **********************************************************/ public void insertRandomlyBelow( int key ) { boolean goLeft = generator.nextInt( 2 ) == 0;

if ( goLeft ) // randomly chose to insert to the left { if ( left != null ) // move to the left child (which exists) left.insertRandomlyBelow( key ); else // no left child, so insert! left = new Node( key ); } else // randomly chose to insert to the right { if ( right != null ) // move to the right child (which exists) right.insertRandomlyBelow( key ); else // no right child, so insert! right = new Node( key ); } } // end insertRandomlyBelow

/********************************************************* * Print the tree in an inorder traversal **********************************************************/ public void printTree( ) { if ( left != null ) left.printTree();

System.out.print( " " + data );

if ( right != null ) right.printTree(); }

/********************************************************* * isOrdered (a RECURSIVE method) * * Returns true if the tree is in binary search tree order * and false otherwise. **********************************************************/ public boolean isOrdered() { //===============> YOUR CODE GOES HERE <=============== }

/********************************************************* * getMax (a RECURSIVE method) * * Returns the maximum value stored in the subtree * consisting of this and its descendants. * (Assumes the tree is in BST order.) **********************************************************/ public int getMax() { //===============> YOUR CODE GOES HERE <=============== }

/********************************************************* * getMin (a RECURSIVE method) * * Returns the minimum value stored in the subtree * consisting of this and its descendants. * (Assumes the tree is in BST order.) **********************************************************/ public int getMin() { //===============> YOUR CODE GOES HERE <=============== }

} // end class Node