Implement a Binary Search Tree with Traversal Methods

Hello, I am having trouble with this Java Programming assignment. Any help would be appreciated!

I need to implement the following methods:

public boolean search(E e) //TODO

public void insert(E e) //TODO

public boolean delete(E e) //TODO Note: User inorder successor to replace the deleted node

public ArrayList postorderNoRecursion() //TODO Note: Do not use recursion

public int getNumberofNonLeaves() //TODO

public ArrayList inorderNoRecursion() //TODO Note: Do not use recursion

as well as take input from the following text file:

input.txt:

INS THREE //Insert Node with value "3" in the tree INS ONE //Insert Node with value "1" in the tree INS TWO //Insert Node with value "2" in the tree INS EIGHT //Insert Node with value "8" in the tree INS FOUR //Insert Node with value "4" in the tree SEARCH THREE //Search node with value "3" in tree DEL FOUR //Delete node with value "4" from the tree COUNT NON_LEAF //Count non-leaf nodes in the tree GET NON_REC_IN //Get inorder traversal of the tree without recursion GET NON_REC_POST //Get postorder traversal of the tree without recursion

Necessary Java Files:

BST.java:

import java.util.ArrayList; import java.util.Stack;

/** * NAME: abstractTree.java Description: This is the BST class containing all * methods for traversing the tree Author: */

public class BST> implements TreeInterface {

// Data fields public TreeNode rootTreeNode=null; // Store the number of Nodes in this class variables public int size = 0; // Store the number of Non Leaf nodes in this class variables public int nonleaves;

public ArrayList inOrderTraversal = new ArrayList<>(); public ArrayList preOrderTraversal = new ArrayList<>(); public ArrayList postOrderTraversal = new ArrayList<>(); public ArrayList bstTraversal = new ArrayList<>();

// empty constructor public BST() { }

// Looks for an item in the tree public boolean search(E e) { boolean blResult = false;

/** * TODO: INSERT YOUR CODE HERE * * SEARCH FOR THE ITEM PASSED AS PARAMETER AND RETURN TRUE IF FOUND ELSE RETURN * FALSE * * */ return blResult; } // end search method

public void insert(E e) {

/** * TODO: INSERT YOUR CODE HERE * * INSERT THE ITEM PASSED AS PARAMETER IN THE TREE . HINT: THE NUMBER OF NODE * CAN BE UPDATED IN THE "size" VARIABLE * */

}

public boolean delete(E e) { boolean blResult = false; /** * TODO: INSERT YOUR CODE HERE DELETE THE ITEM PASSED AND REPLACE WITH THE * INORDER SUCCESSOR OF THE ELEMENT RETURN true IF ELEMENT FOUND AND DELETED * ELSE RETURN false i.e. ITEM NOT FOUND HINT: THE NUMBER OF NODE CAN BE UPDATED * IN THE "size" VARIABLE HINT: SEARCH FOR THE ELEMENT TO BE DELETED AND DELETE * THE ELEMENT ONCE FOUND * */ return blResult; }

// (Implement postorder traversal without using recursion) public ArrayList postorderNoRecursion() { ArrayList nonRecursivePostorder = new ArrayList<>();

/** * TODO: INSERT YOUR CODE HERE FIND THE POST ORDER TRAVERSAL OF THE TREE WITHOUT * USING RECURSION AND RETURN THE RESULT TRAVEL SEQUENCE IN ARRAYLIST * nonRecursivePostorder */

return nonRecursivePostorder; }

// get the Number of non-leaves. public int getNumberofNonLeaves() { /** * TODO: INSERT YOUR CODE HERE FIND THE NUMBER OF NON_LEAF NODES IN THE TREE AND * RETURN */ return nonleaves; }

// (Implement inorder traversal without using recursion) public ArrayList inorderNoRecursion() { ArrayList nonRecursiveInorder = new ArrayList<>();

/** * TODO: INSERT YOUR CODE HERE FIND THE IN ORDER TRAVERSAL OF THE TREE WITHOUT * USING RECURSION AND RETURN THE RESULT TRAVEL SEQUENCE IN ARRAYLIST * nonRecursiveInorder */

return nonRecursiveInorder; }

}// end class BST

TreeNode.java:

/** * NAME: TreeNode.java Description: creates the node with root, left and right * children defined * */

class TreeNode { Object element; TreeNode left; TreeNode right;

public TreeNode() {

}

public Object getElement() { return element; }

public void setElement(Object element) { this.element = element; }

public TreeNode getLeft() { return left; }

public void setLeft(TreeNode left) { this.left = left; }

public TreeNode getRight() { return right; }

public void setRight(TreeNode right) { this.right = right; }

// end TreeNode

}// end class TreeNode

TreeInterface.java:

import java.util.ArrayList;

/** * NAME: Tree.java Description: interface with abstract methods * */

public interface TreeInterface {

/** Return true if the element is in the tree */ public boolean search(E e);

/** * Insert element o into the binary tree Return true if the element is inserted * successfully */ public void insert(E e);

/** * Delete the specified element from the tree Return true if the element is * deleted successfully */ public boolean delete(E e);

/** Return the Number of non-leaves. */ public int getNumberofNonLeaves();

/** Return inorder traversal using stack i.e. without using recursion */ public ArrayList inorderNoRecursion();

/** Return postorder traversal using stack i.e. without using recursion */ public ArrayList postorderNoRecursion(); }// end interface Tree

Test.java:

import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.List; import java.util.Scanner;

public class Test { public static void main(String[] args) throws FileNotFoundException {

File file = new File("input.txt"); if (!file.isFile()) file = new File("src/input.txt"); BST objTest = new BST(); Scanner sc = new Scanner(file);

while (sc.hasNext()) { String operation = sc.next(); String nodeValue = sc.next();

if ("INS".equalsIgnoreCase(operation)) { objTest.insert(nodeValue); } else if ("DEL".equalsIgnoreCase(operation)) { objTest.delete(nodeValue); } else if ("COUNT".equalsIgnoreCase(operation)) { if ("NON_LEAF".equalsIgnoreCase(nodeValue)) { System.out.println(objTest.getNumberofNonLeaves()); }

} else if ("SEARCH".equalsIgnoreCase(operation)) { System.out.println(objTest.search(nodeValue));

} else if ("GET".equalsIgnoreCase(operation)) { if ("NON_REC_IN".equalsIgnoreCase(nodeValue)) { printTraversal(objTest.inorderNoRecursion()); } else if ("NON_REC_POST".equalsIgnoreCase(nodeValue)) { printTraversal(objTest.postorderNoRecursion()); }

}

} sc.close(); }

public static void printTraversal(ArrayList arr) { System.out.println(""); for (int i = 0; i < arr.size(); i++) { System.out.print(arr.get(i)); } }

}