I need to implement a binary search tree (BST) which stores integers that you wi
ID: 3832712 • Letter: I
Question
I need to implement a binary search tree (BST) which stores integers that you will read from a file. Your BST will have an add, delete, print, find, and rangeFind function. This assignment is based on common job interview questions that involve BST.
Extra Credit: Implement with node heights. Use the height to print the tree with branch lengths.
Example I/O: Without errors: File name: numbers.txt Delete (d), Print (p), Find (f), RangeFind (r), Quit (q) p 3 5 6 7 8 10 11 13 15 16 17 19 20 23 24 26 29 30 34 34 40 f Find: 20 Value found f Find: 29 Value found f Find: 18 Value not found. The closest value is: 17 f Find: 90 Value not found. The closest value is: 40 r Range Min: 11 Range Max: 22 11 13 15 16 17 19 20 d Delete: 43 43 Not found in BST. d Delete: 7 p 3 5 6 8 10 11 13 15 16 17 19 20 23 24 26 29 30 34 34 40 q
Explanation / Answer
Hi, I have implemented basic methods of BST, inorder, countNode, insert, height.
Please repost for other functionality.
import java.io.File;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
public class BinarySearchTree {
/* Class containing left and right child of current node and key value */
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
public int countNode(Node root){
if(root == null)
return 0;
else
return 1 + countNode(root.left) + countNode(root.right);
}
public int height(Node node){
if(node == null)
return 0;
int lh = height(node.left);
int rh = height(node.right);
if(lh > rh)
return lh + 1;
else
return rh +1;
}
// Driver Program to test above functions
public static void main(String[] args) throws IOException {
BinarySearchTree tree = new BinarySearchTree();
Scanner sc = new Scanner(System.in);
System.out.println("Enter input file name: ");
String fileName = sc.next();
Scanner fileScanner = new Scanner(new File(fileName));
while(fileScanner.hasNextInt()){
int N = fileScanner.nextInt();
tree.insert(N);
}
fileScanner.close();
sc.close();
tree.inorder();
sc.close();
}
}