1. Add the function int nodeLevel (T value) to the Binary Search Tree class that returns the level of the node in the Binary Search Tree. Integrate the code with the code provided. Submit code and sample output.
2. Add the member functions pre-order and post-order traversals to the Binary Search Tree class. Write code to test the functions. Submit code and sample output

I think i have the functions correct in the BinarySearchTree.java class. Now i'm trying to show it in the demo file.

// BinarySearchTree.java

class BinarySearchTree { private Node root; public BinarySearchTree() { root = null; } public Node getRoot() { return root; } public Node search(int desiredKey) { Node currentNode = root; while (currentNode != null) { // Return the node if the key matches if (currentNode.key == desiredKey) { return currentNode; } // Navigate to the left if the search key is // less than the node's key. else if (desiredKey < currentNode.key) { currentNode = currentNode.left; } // Navigate to the right if the search key is // greater than the node's key. else { currentNode = currentNode.right; } } // The key was not found in the tree. return null; } public void insert(Node node) { // Check if tree is empty if (root == null) { root = node; } else { Node currentNode = root; while (currentNode != null) { if (node.key < currentNode.key) { // If no left child exists, add the new node // here; otherwise repeat from the left child. if (currentNode.left == null) { currentNode.left = node; currentNode = null; } else { currentNode = currentNode.left; } } else { // If no right child exists, add the new node // here; otherwise repeat from the right child. if (currentNode.right == null) { currentNode.right = node; currentNode = null; } else { currentNode = currentNode.right; } } } } } public boolean remove(int key) { Node parent = null; Node currentNode = root; // Search for the node. while (currentNode != null) { // Check if currentNode has a matching key. if (currentNode.key == key) { if (currentNode.left == null && currentNode.right == null) { if (parent == null) { // Node is root root = null; } else if (parent.left == currentNode) { parent.left = null; } else { parent.right = null; } return true; // Node found and removed } else if (currentNode.left != null && currentNode.right == null) { if (parent == null) { // Node is root root = currentNode.left; } else if (parent.left == currentNode) { parent.left = currentNode.left; } else { parent.right = currentNode.left; } return true; // Node found and removed } else if (currentNode.left == null && currentNode.right != null) { if (parent == null) { // Node is root root = currentNode.right; } else if (parent.left == currentNode) { parent.left = currentNode.right; } else { parent.right = currentNode.right; } return true; // Node found and removed } else { // Find successor (leftmost child of right subtree) Node successor = currentNode.right; while (successor.left != null) { successor = successor.left; } currentNode.key = successor.key; // Copy successor to current node parent = currentNode; currentNode = currentNode.right; // Remove successor from right subtree key = successor.key; // Loop continues with new key } } else if (currentNode.key < key) { // Search right parent = currentNode; currentNode = currentNode.right; } else { // Search left parent = currentNode; currentNode = currentNode.left; } } return false; // Node not found } // ************** HW #3 add function: int nodeLevel ********************** public int nodeLevel(int value) { return getLevelUtil(root, value, 1); }

// ************** HW #3 add function: preorder & postorder **********************

public void displayPreorder(Node node) { if (node == null) { return; } System.out.print(node.key + " "); displayPreorder(node.left); displayPreorder(node.right); }

public void displayPostorder(Node node) { if (node == null) { return; } displayPostorder(node.left); displayPostorder(node.right); System.out.print(node.key + " "); }

private int getLevelUtil(Node node, int data, int level) { if (node == null) { return 0; } if (node.key == 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; } }

// ***************BinarySearchTreeDemo.java*********************

import java.util.Scanner;

public class BinarySearchTreeDemo { public static void main(String[] args) { Scanner scnr = new Scanner(System.in); BinarySearchTree tree = new BinarySearchTree(); // Ask user for values to insert System.out.print("Enter values to insert with spaces between: "); String userValues = scnr.nextLine(); System.out.println(); // Add each value to the tree for (String value : userValues.split(" ")) { int key = Integer.parseInt(value); tree.insert(new Node(key)); } // Show the tree System.out.println("Initial tree:"); System.out.println(BSTPrint.treeToString(tree.getRoot())); System.out.println(); // show the level of the entered level

System.out.println("Enter node to find level");

// show preorder here....

// show postorder here

} }