Question

import java.util.ArrayList;

/*
Rules:
        1. Allow Tester to iterate through all nodes using the in-order traversal as the default.
            This means, in Tester the following code should work for an instance of this class
            called bst that is storing Student objects for the data:

                BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();
                bst.add("Man");       bst.add("Soda");   bst.add("Flag");
                bst.add("Home");   bst.add("Today");   bst.add("Jack");

                for(String s : bst)
                    System.out.println(s);

        2.   You can not use a size variable to keep track of the number of nodes
*/

/**
* Lab-08: BinarySearchTree Implementation
*
* @author
*
*/

public class BinarySearchTree_Lab08<T> {
   //====================================================================================== Properties
   private Node root;

   //====================================================================================== Constructors
   public BinarySearchTree_Lab08() {

   }

   // Constructor that takes an array of items and populates the tree
   public BinarySearchTree_Lab08(T[] items) {

   }

   //====================================================================================== Methods
   public void add(T data) {   // Implement recursively and do NOT allow duplicates

   }

   // Returns the traversal of this tree as an array
   public ArrayList<T> preOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       preOrder_Traversal(root, data);  
       return data;
   }
   private void preOrder_Traversal(Node n, ArrayList<T> data) {
      
   }

   public ArrayList<T> inOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       inOrder_Traversal(root, data);  
       return data;
   }
   private void inOrder_Traversal(Node n, ArrayList<T> data) {
      
   }

   public ArrayList<T> postOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       postOrder_Traversal(root, data);  
       return data;  
   }
   private void postOrder_Traversal(Node n, ArrayList<T> data) {
      
   }

   public ArrayList<T> breadthFirst_Traversal() {
       return null;
   }

   // Since this is a binary SEARCH tree, you should write
   // an efficient solution to this that takes advantage of the order
   // of the nodes in a BST. Your algorithm should be, on average,
   // O(h) where h is the height of the BST.
   public boolean contains(T data) {
       return false;
   }

   // returns the smallest value in the tree
   // or throws an IllegalStateException() if the
   // tree is empty. Write the recursive version
   public T min() { return min(root); }       // this method is done for you.      
   private T min(Node n) {   // Write this method.
       return null;
   }

   // returns the largest value in the tree
   // or throws an IllegalStateException() if the
   // tree is empty. Write the recursive version
   public T max() { return max(root); }       // this method is done for you.
   private T max(Node n) {   // Write this method.
       return null;
   }

   // Returns whether the tree is empty
   public boolean isEmpty() {
       return false;
   }

   // returns the height of this BST. If a BST is empty, then
   // consider its height to be -1.
   public int getHeight() {
       return -1;
   }

   // returns the largest value of all the leaves
   // If the tree is empty, throw an IllegalStateException()
   // Note, this is different than max as this is the max
   // of all leaf nodes
   public T maxLeaf() {
       return null;
   }

   // counts the number of nodes in this BST
   public int nodeCount() {
       return -1;
   }

   // returns the "level" of the value in a tree.
   // the root is considered level 0
   // the children of the root are level 1
   // the children of the children of the root are level 2
   // and so on. If a value does not appear in the tree, return -1
   // 15
   // / \
   // 10 28
   // \ \
   // 12 40
   // /
   // 30
   // In the tree above:
   // getLevel(15) would return 0
   // getLevel(10) would return 1
   // getLevel(30) would return 3
   // getLevel(8) would return -1
   public int getLevel(T n) {
       return -1;
   }

   // A tree is height-balanced if at each node, the heights
   // of the node's two subtrees differs by no more than 1.
   // Special note about null subtrees:
   // 10
   // \
   // 20
   // Notice in this example that 10's left subtree is null,
   // and its right subtree has height 0. We would consider this
   // to be a balanced tree. If the tree is empty, return true;
   public boolean isBalanced() {
       return false;
   }

   //====================================================================================== Inner Node Class
   private class Node {
       private T data;
       private Node left, right;

       private Node(T data) {
           this.data = data;
           left = right = null;
       }
   }
}

import java.util.Arrays;

public class Tester {

   public static void main(String[] args) {
       BinarySearchTree_Lab08<Integer> bst = new BinarySearchTree_Lab08<Integer>();
      
       bst.add(25);      
       bst.add(12);  
       bst.add(80);
       bst.add(8);  
       bst.add(20);  
       bst.add(63);
       bst.add(12);   //   should not be added
       bst.add(25);   //   should not be added
       bst.add(90);
       bst.add(20);   //   should not be added
       bst.add(44);
       bst.add(73);
       bst.add(85);
       bst.add(71);

       System.out.println("Pre-Order : " + bst.preOrder_Traversal());
       System.out.println("In-Order : " + bst.inOrder_Traversal());
       System.out.println("Post-Order : " + bst.postOrder_Traversal());
       System.out.println("Breadth First: " + bst.breadthFirst_Traversal());
       /*
           Pre-Order   : 25 12 8 20 80 63 44 73 71 90 85
           In-Order : 8 12 20 25 44 63 71 73 80 85 90
           Post-Order : 8 20 12 44 71 73 63 85 90 80 25
           Breadth First: 25 12 80 8 20 63 90 44 73 85 71
       */
      
       System.out.println("Height : " + bst.getHeight());    // 4
       System.out.println("Contains(44) : " + bst.contains(44));    // true
       System.out.println("Contains(99) : " + bst.contains(99));    // false
       System.out.println("getLevel(73) : " + bst.getLevel(73));    // 3
       System.out.println("getLevel(99) : " + bst.getLevel(99));    // -1
       System.out.println("isBalanced() : " + bst.isBalanced());    // false
       System.out.println("isEmpty() : " + bst.isEmpty());        // false
       System.out.println("maxLeaf() : " + bst.maxLeaf());        // 85
       System.out.println("nodeCount() : " + bst.nodeCount());    // 11
       System.out.println("min() : " + bst.min());            // 8
       System.out.println("max() : " + bst.max());            // 90

      
       /* Uncomment the following loop after setting up the
       * BinarySearchTree_Lab08 for iteration */
       System.out.print("For Each Loop: ");
//       for(int s : bst)
//           System.out.print(s + " ");           // 8 12 20 25 44 63 71 73 80 85 90
   }
}

Answer 1

****************************************************************************

Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.

*******************************************************************************/

import java.util.ArrayList;

/*
Lab-08: BinarySearchTree Implementation

Rules:
1. Allow Tester to iterate through all nodes using the in-order traversal as the default.
This means, in Tester the following code should work for an instance of this class
called bst that is storing Student objects for the data:

BinarySearchTree_Lab08 bst = new BinarySearchTree_Lab08();
bst.add("Man"); bst.add("Soda"); bst.add("Flag");
bst.add("Home"); bst.add("Today"); bst.add("Jack");

for(String s : bst)
System.out.println(s);

2. You can not use a size variable to keep track of the number of nodes

3. You CAN (for extra credit) create a JUnit test - needs to be 100% complete
(if you do a JUnit test you need to also upload it)
*/

/**
* Lab-08: BinarySearchTree Implementation
*
* @author
*
*/

public class BinarySearchTree_Lab08 {
//====================================================================================== Properties

private Node root;

//====================================================================================== Constructors
public BinarySearchTree_Lab08() {
root = null;
}

// Constructor that takes an array of items and populates the tree
public BinarySearchTree_Lab08(T[] items) {
for(int i = 0; i < items.length();i++){
root = add_recursive(root, items[i]);
}
}

//====================================================================================== Methods

Node add_recursive(Node root, int key){
if (root == null) {
root = new Node(key);
return root;
}
//traverse the tree
if (key < root.key) //insert in the left subtree
root.left = add_recursive(root.left, key);
else if (key > root.key) //insert in the right subtree
root.right = add_recursive(root.right, key);
// return pointer
return root;
}

// Returns the traversal of this tree as an array
public ArrayList preOrder_Traversal() {  
ArrayList data = new ArrayList();
preOrder_Traversal(root, data);  
return data;
}
private void preOrder_Traversal(Node root, ArrayList data) {
if (root != null) {
data.add(root.key);
preOrder_Traversal(root.left);
preOrder_Traversal(root.right);
}
}

public ArrayList inOrder_Traversal() {  
ArrayList data = new ArrayList();
inOrder_Traversal(root, data);  
return data;
}
private void inOrder_Traversal(Node n, ArrayList data) {
if (root != null) {
inOrder_Traversal(root.left);
data.add(root.key);
inOrder_Traversal(root.right);
}
}

public ArrayList postOrder_Traversal() {  
ArrayList data = new ArrayList();
postOrder_Traversal(root, data);  
return data;  
}
private void postOrder_Traversal(Node n, ArrayList data) {
if (root != null) {
postOrder_Traversal(root.left);
postOrder_Traversal(root.right);
data.add(root.key);
}
}

public ArrayList breadthFirst_Traversal() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
ArrayList items = new ArrayList();
  
while (!queue.isEmpty())  
{
  
Node tempNode = queue.poll();
items.add(tempNode.key);
  
/*Enqueue left child */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
  
/*Enqueue right child */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
return items;
}

// Since this is a binary SEARCH tree, you should write
// an efficient solution to this that takes advantage of the order
// of the nodes in a BST. Your algorithm should be, on average,
// O(h) where h is the height of the BST.
public boolean contains(T data) {
root = search_Recursive(root, key);
if (root!= null)
return true;
else
return false;
}
Node search_Recursive(Node root, int key) {
// Base Cases: root is null or key is present at root
if (root==null || root.key==key)
return root;
// val is greater than root's key
if (root.key > key)
return search_Recursive(root.left, key);
// val is less than root's key
return search_Recursive(root.right, key);
}
// returns the smallest value in the tree
// or throws an IllegalStateException() if the
// tree is empty. Write the recursive version
public T min() { return min(root); } // this method is done for you.   
private T min(Node n) { // Write this method.
int minval = root.key;
//find minval
while (root.left != null) {
minval = root.left.key;
root = root.left;
}
return minval;
}

// returns the largest value in the tree
// or throws an IllegalStateException() if the
// tree is empty. Write the recursive version
public T max() { return max(root); } // this method is done for you.
private T max(Node n) { // Write this method.
int maxval = root.key;
//find minval
while (root.right != null) {
maxval = root.right.key;
root = root.right;
}
return maxval;
}

// Returns whether the tree is empty
public boolean isEmpty() {
return root == null;
}

// returns the height of this BST. If a BST is empty, then
// consider its height to be -1.
public int getHeight() {
return find_height(root);
}

private int find_height(Node root){
if(root == null)
return 0;
int l_height = find_height(root.left);
int r_height = find_height(root.right);
return max(l_height, r_height) + 1;
}

// returns the largest value of all the leaves
// If the tree is empty, throw an IllegalStateException()
// Note, this is different than max as this is the max
// of all leaf nodes
public T maxLeaf() {
if (root == null)
throw new IllegalStateException("Tree is empty");
int mxm = -20000;
return max_leaf(root, mxm);
}

private void max_leaf(Node root, int &mxm){
if(root == null)
return -200000;
max_leaf(root.left, mxm);
if(root.left == null and root.right == null)
mxm = max(mxm, root.key);
max_leaf(root.right);
  
  
}

// counts the number of nodes in this BST
public int nodeCount() {
return node_count(root);
}
private int node_count(Node root){
if(root == null)
return 0;
int l_count = node_count(root.left);
int r_count = node_count(root.right);
return l_count + r_count + 1;
}

// returns the "level" of the value in a tree.
// the root is considered level 0
// the children of the root are level 1
// the children of the children of the root are level 2
// and so on. If a value does not appear in the tree, return -1
// 15
// / \
// 10 28
// \ \
// 12 40
// /
// 30
// In the tree above:
// getLevel(15) would return 0
// getLevel(10) would return 1
// getLevel(30) would return 3
// getLevel(8) would return -1
public int getLevel(T n) {
return -1;
}

// *********************************************************
// EXTRA CREDIT: 5pts
// *********************************************************
// A tree is height-balanced if at each node, the heights
// of the node's two subtrees differs by no more than 1.
// Special note about null subtrees:
// 10
// \
// 20
// Notice in this example that 10's left subtree is null,
// and its right subtree has height 0. We would consider this
// to be a balanced tree. If the tree is empty, return true;
public boolean isBalanced() {
return isBalanced(root);
}
private boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */
  
int rh; /* for height of right subtree */
  
/* If tree is empty then return true */
if (node == null)
return true;
  
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
  
if (Math.abs(lh - rh) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right))
return true;
  
/* If we reach here then tree is not height-balanced */
return false;
}

//====================================================================================== Inner Node Class
private class Node {
private T data;
private Node left, right;

private Node(T data) {
this.data = data;
left = right = null;
}
}
}

import java.util.Arrays;

public class Tester {

public static void main(String[] args) {
BinarySearchTree_Lab08 bst = new BinarySearchTree_Lab08();
  
bst.add(25);   
bst.add(12);  
bst.add(80);
bst.add(8);  
bst.add(20);  
bst.add(63);
bst.add(12); // should not be added
bst.add(25); // should not be added
bst.add(90);
bst.add(20); // should not be added
bst.add(44);
bst.add(73);
bst.add(85);
bst.add(71);

System.out.println("Pre-Order : " + bst.preOrder_Traversal());
System.out.println("In-Order : " + bst.inOrder_Traversal());
System.out.println("Post-Order : " + bst.postOrder_Traversal());
System.out.println("Breadth First: " + bst.breadthFirst_Traversal());
/*
Pre-Order : 25 12 8 20 80 63 44 73 71 90 85
In-Order : 8 12 20 25 44 63 71 73 80 85 90
Post-Order : 8 20 12 44 71 73 63 85 90 80 25
Breadth First: 25 12 80 8 20 63 90 44 73 85 71
*/
  
System.out.println("Height : " + bst.getHeight()); // 4
System.out.println("Contains(44) : " + bst.contains(44)); // true
System.out.println("Contains(99) : " + bst.contains(99)); // false
System.out.println("getLevel(73) : " + bst.getLevel(73)); // 3
System.out.println("getLevel(99) : " + bst.getLevel(99)); // -1
System.out.println("isBalanced() : " + bst.isBalanced()); // false
System.out.println("isEmpty() : " + bst.isEmpty()); // false
System.out.println("maxLeaf() : " + bst.maxLeaf()); // 85
System.out.println("nodeCount() : " + bst.nodeCount()); // 11
System.out.println("min() : " + bst.min()); // 8
System.out.println("max() : " + bst.max()); // 90

  
/* Uncomment the following loop after setting up the
* BinarySearchTree_Lab08 for iteration */
System.out.print("For Each Loop: ");
// for(int s : bst)
// System.out.print(s + " "); // 8 12 20 25 44 63 71 73 80 85 90
}
}

Comment