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:

if this answer is helpful to you please give positive rating.if any doubts please provide comments i will clarify your doubts...