Question

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<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;
       }
   }
}

Answer 1

/**
 * This file contains an implementation of a Binary Search Tree (BST) Any comparable data is allowed
 * within this tree (numbers, strings, comparable Objects, etc...). Supported operations include
 * adding, height,isBalanced and containment checks. Furthermore, multiple tree traversal Iterators
 * are provided including: 1) Preorder traversal 2) Inorder traversal 3) Postorder traversal 4)
 * BFS traversal
 *
 */

import java.util.ArrayList;

class BinarySearchTree_Lab08<T extends Comparable<T>> {

    public BinarySearchTree_Lab08() {
    
    }

   // Constructor that takes an array of items and populates the tree
   public BinarySearchTree_Lab08(T[] items) {
        for(T item : items) { 
                add(item);
        }    
   }

  // Tracks the number of nodes in this BST
  private int nodeCount = 0;

  // This BST is a rooted tree so we maintain a handle on the root node
  private Node root = null;

  // Internal node containing node references
  // and the actual node data
  private class Node {
    T data;
    Node left, right;

    public Node(Node left, Node right, T elem) {
      this.data = elem;
      this.left = left;
      this.right = right;
    }
  }

  // Check if this binary tree is empty
  public int isEmpty() {
    return nodeCount() == 0 ? nodeCount() : -1;
  }

  // Get the number of nodes in this binary tree
  public int nodeCount() {
    return nodeCount;
  }

  // Add an element to this binary tree. Returns true
  // if we successfully perform an insertion
  public boolean add(T elem) {

    // Check if the value already exists in this
    // binary tree, if it does ignore adding it
    if (contains(elem)) {
      return false;

      // Otherwise add this element to the binary tree
    } else {
      root = add(root, elem);
      nodeCount++;
      return true;
    }
  }

  // Private method to recursively add a value in the binary tree
  private Node add(Node node, T elem) {

    // Base case: found a leaf node
    if (node == null) {
      node = new Node(null, null, elem);

    } else {
      // Pick a subtree to insert element
      if (elem.compareTo(node.data) < 0) {
        node.left = add(node.left, elem);
      } else {
        node.right = add(node.right, elem);
      }
    }
    return node;
  }

  // Helper method to find the leftmost node (which has the smallest value)
  private Node findMin(Node node) {
    while (node.left != null) node = node.left;
    return node;
  }
  //return the min node
  public T findMin() {
    Node node = findMin(root);
    return node.data;
  }

  // Helper method to find the rightmost node (which has the largest value)
  private Node findMax(Node node) {
    while (node.right != null) node = node.right;
    return node;
  }
  //return the max node
  public T findMax() {
    Node node = findMax(root);
    return node.data;
  }

  // returns true is the element exists in the tree
  public boolean contains(T elem) {
    return contains(root, elem);
  }

  // private recursive method to find an element in the tree
  private boolean contains(Node node, T elem) {

    // Base case: reached bottom, value not found
    if (node == null) return false;

    int cmp = elem.compareTo(node.data);

    // Dig into the left subtree because the value we're
    // looking for is smaller than the current value
    if (cmp < 0) return contains(node.left, elem);

    // Dig into the right subtree because the value we're
    // looking for is greater than the current value
    else if (cmp > 0) return contains(node.right, elem);

    // We found the value we were looking for
    else return true;
  }

  // Computes the height of the tree, O(n)
  public int height() {
    return height(root);
  }

  // Recursive helper method to compute the height of the tree
  private int height(Node node) {
    if (node == null) return 0;
    return Math.max(height(node.left), height(node.right)) + 1;
  }
  
  /* Helper function for getLevel().  
    It returns level of the data if data is 
    present in tree, otherwise returns 0.*/
    private int getLevelUtil(Node node,T data, int level) 
    { 
        if (node == null) 
            return 0; 
      
        if (node.data == data) 
            return level; 
      
        int downlevel = getLevelUtil(node.left,data,level + 1); 
        if (downlevel != 0) 
            return downlevel; 
      
        downlevel = getLevelUtil(node.right,data,level + 1); 
        return downlevel; 
    } 
      
    /* Returns level of given data value */
    public int getLevel(T data) 
    { 
        if( contains(data) ){
            return getLevelUtil(root, data, 1);    
        }
        return -1;
    }
    
    // Helper method to find the max value leaf node (which has the largest value)
      private Node maxLeaf(Node node) {
        while (node.right != null) node = node.right;
        return node;
      }
      //return the max leaf node 
      public T maxLeaf() {
        Node node = maxLeaf(root);
        return node.data;
      }
    
    // Helper method to find the tree is height balanced or not
    private boolean isBalancedUtil(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
            && isBalancedUtil(node.left) 
            && isBalancedUtil(node.right)) 
            return true; 
  
        /* If we reach here then tree is not height-balanced */
        return false; 
    }
    
    /* Returns true if binary tree with root as root is height-balanced */
    public boolean isBalanced() 
    { 
        return isBalancedUtil(root);
    }
    
    /* Given a binary tree, get its nodes according to the 
      "bottom-up" postorder traversal. */
    private void postOrder_Traversal(Node node,ArrayList<T> data) 
    { 
        if (node == null) 
            return; 
  
        // first recur on left subtree 
        postOrder_Traversal(node.left,data); 
  
        // then recur on right subtree 
        postOrder_Traversal(node.right,data); 
  
        // now add data to array 
        data.add(node.data);  
    } 
  
    /* Given a binary tree, get its nodes in inorder*/
    private void inOrder_Traversal(Node node,ArrayList<T> data) 
    { 
        if (node == null) 
            return; 
  
        /* first recur on left child */
        inOrder_Traversal(node.left,data); 
  
        /* then add data to array */
        data.add(node.data); 
  
        /* now recur on right child */
        inOrder_Traversal(node.right,data); 
    } 
  
    /* Given a binary tree, get its nodes in preorder*/
    private void preOrder_Traversal(Node node,ArrayList<T> data) 
    { 
        if (node == null) 
            return; 
  
        /* first add data to array */
        data.add(node.data); 
  
        /* then recur on left sutree */
        preOrder_Traversal(node.left,data); 
  
        /* now recur on right subtree */
        preOrder_Traversal(node.right,data); 
    } 
    
    /* Helper Function to Get nodes at the BFS Order */
    private void breadthFirst_TraversalUtil(Node node,int level,ArrayList<T> data) 
    { 
        if (node == null) 
            return; 
        if (level == 1) 
            data.add(node.data); 
        else if (level > 1) 
        { 
            breadthFirst_TraversalUtil(node.left, level-1,data); 
            breadthFirst_TraversalUtil(node.right, level-1,data); 
        } 
    } 
    
    /* function to get BFS order traversal of tree*/
    private void breadthFirst_Traversal(Node node,ArrayList<T> data) 
    { 
        int h = height(); 
        int i; 
        for (i=1; i<=h; i++) 
            breadthFirst_TraversalUtil(root, i,data); 
    } 

  // Returns the traversal of this tree as an array
   // Pre Order Traversal
   public ArrayList<T> preOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       preOrder_Traversal(root, data);  
       return data;
   }
   // In Order Traversal    
   public ArrayList<T> inOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       inOrder_Traversal(root, data);  
       return data;
   }

   // Post Order Traversal
   public ArrayList<T> postOrder_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       postOrder_Traversal(root, data);  
       return data;  
   }
   
   // BFS Search Order
   public ArrayList<T> breadthFirst_Traversal() {  
       ArrayList<T> data = new ArrayList<T>();
       breadthFirst_Traversal(root,data);  
       return data;
   }
}

public class Main{
    public static void main(String args[]){
        //Creating Object Without Constructor Parameters
        BinarySearchTree_Lab08<Integer> tree = new BinarySearchTree_Lab08<Integer>();
        System.out.println("Initialize Tree Values Without Using Constructor: ");
        tree.add(1);
        tree.add(2);
        tree.add(3);
        tree.add(4);
        tree.add(5);
        ArrayList<Integer> data = new ArrayList<Integer>();
        //Pre Order Traversal
        System.out.print("Pre Order Traversal: ");
        data = tree.preOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        //In Order Traversal
        System.out.println("");
        System.out.print("In Order Traversal: ");
        data = tree.inOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        //Post Order Traversal
        System.out.println("");
        System.out.print("Post Order Traversal: ");
        data = tree.postOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        
        //BFS Order Traversal 
        System.out.println("");
        System.out.print("BFS Order Traversal: ");
        data = tree.breadthFirst_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        System.out.println("");
        
        //Creating Object Using Constructor Parameters
        BinarySearchTree_Lab08<Integer> tree1 = new BinarySearchTree_Lab08<Integer>(new Integer[] {1,2,3,4,5});
        System.out.println("Initialize Tree Values Using Constructor: ");
        //Pre Order Traversal
        System.out.print("Pre Order Traversal: ");
        data = tree1.preOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        //In Order Traversal
        System.out.println("");
        System.out.print("In Order Traversal: ");
        data = tree1.inOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        //Post Order Traversal
        System.out.println("");
        System.out.print("Post Order Traversal: ");
        data = tree1.postOrder_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
        
        //BFS Order Traversal 
        System.out.println("");
        System.out.print("BFS Order Traversal: ");
        data = tree1.breadthFirst_Traversal();
        for (int i = 0; i < data.size(); i++){ 
            System.out.print(data.get(i) + " "); 
        }
    }
}

Output: