Binary trees

Assignment

Overview

Develop an interactive software that builds a binary search tree, perform standard operations on
the tree and its nodes.

Project Description

The software can build a binary search tree from a series of number input by users. It can performretrieval, insertion and deletions of entries, standard traversals and data processing.

Functional Requirements

A user can, by using a command prompt to do the following:
1. Build a binary search tree by giving a series of number.
2. After the BST is built, the user can see following traversal printed to the output file, and
displayed on the screen:
a. Preorder.
b. Inorder.
c. Postorder.
3. Insert an entry to the binary search tree.. After the operation, the user can see the new
binary search tree traversed in an Inorder traversal printed to output file and displayed on
the screen.
4. Delete an entry. After the operation, the user can see the new binary search tree traversed
in an Inorder traversal printed to output file and displayed on the screen.
5. Retrieve, display and print the inorder predecessor of a given entry input by the user.
6. Retrieve, display and print the inorder successor of a given entry input by the user.
7. Seek command help of this software by entering the letter H. The command line commands
are:
H Display Help
I Insert a value
D Delete a value
P Find predecessor
S Find successor
E Exit the program
8. Be informed when input data are invalid.
Engineering Requirements

  1. The software must be implemented in Java language.
    2. The software must be written from scratch and use minimum Java library. Use excessive
    Java library will impact the points of this project you will get.
    3. The software must be able to read:
    a. a series of integer entered by a user;
    b. a line of command entered by a user.
    4. Insert and Delete functions/methods must use recursion. Otherwise, the developer will lose
    major points of this project.
    5. The output file’s name is: output.txt.
    6. The software must be able to handle input that are invalid.
    7. The software must inform user if it can’t execute the command line.
    8. The source codes should follow Java programming standard.
    9. Programming best practices should be applied (ref. Lecture 1).

Non-Functional Requirements

None.
Scope

  1. No duplicate entries are allowed in the binary search tree.
    2. Use the command line for user to provide information the software required.
    3. The BST entries are integer.

Expected Results

Below is the content and the format expected for both output file and screen display. The user
inputs are underlined:
% java Project1
Please enter the initial sequence of values:
51 29 68 90 36 40 22 59 44 99 77 60 27 83 15 75 3
Pre-order: X XX … X
In-order: X XX … X
Post-order: X XX … X
Command? H
I Insert a value
D Delete a value
P Find predecessor
S Find successor
E Exit the program
H Display this message
Command? I 88
In-order: X XX … X
Command? I 42
In-order: X XX … X
Command? I 22
22 already exists, ignore.
Command? D 44
In-order: X XX … X
Command? D 90
In-order: X XX … X
Command? D 70
70 doesn’t exist!
Command? D 68
In-order: X XX … X
Command? S 75
77
Command? P 99
88
Command? E
Thank you for using my program!
%
You should test your program with the above data set as well as your own data sets, since it will
be tested against other data sets. For the output submission, please use exactly the same data as
shown above.

Solution

 BST.java

importjava.util.LinkedList;

importjava.util.List;

public class BST {

//To represent a node in a tree

private class BSTNode {

privateint data;

privateBSTNode left;

privateBSTNode right;

publicBSTNode(int data) {

this.data = data;

}

publicintgetData() {

return data;

}

public void setData(int data) {

this.data = data;

}

publicBSTNodegetLeft() {

return left;

}

public void setLeft(BSTNode left) {

this.left = left;

}

publicBSTNodegetRight() {

return right;

}

public void setRight(BSTNode right) {

this.right = right;

}

}

// root of tree and number of elements

privateBSTNode root;

privateint size;

public BST() {

root = null;

size = 0;

}

//add, returns true if added, false if duplicate

publicboolean add(int data) {

return add(data, root);

}

// recursive method to add data to bst

privateboolean add(int data, BSTNode current) {

if (current == null) { // if end

root = new BSTNode(data);

size++;

return true;

} else {

// compare with current

int compare = data – current.getData();

if (compare < 0) {

// add to left if nothing at left

if (current.getLeft() == null) {

current.setLeft(new BSTNode(data));

size++;

return true;

} else {

// recursion

return add(data, current.getLeft());

}

} else if (compare > 0) {

// if no right node

if (current.getRight() == null) {

current.setRight(new BSTNode(data));

size++;

return true;

} else {

return add(data, current.getRight());

}

} else {

return false;

}

}

}

//returns number of elements in a tree

publicint size() {

return size;

}

// preorder traversal

public List<Integer> preorder() {

List<Integer> list = new LinkedList<>();

preorder(list, root);

return list;

}

// recusrive helper for preorder

private void preorder(List<Integer> list, BSTNode current) {

if (current != null) {

list.add(current.getData());

preorder(list, current.getLeft());

preorder(list, current.getRight());

}

}

// postorder traversal

public List<Integer>postorder() {

List<Integer> list = new LinkedList<>();

postorder(list, root);

return list;

}

// recusrive method fropostorder traversal

private void postorder(List<Integer> list, BSTNode current) {

if (current != null) {

postorder(list, current.getLeft());

postorder(list, current.getRight());

list.add(current.getData());

}

}

// inorder traversal

public List<Integer>inorder() {

List<Integer> list = new LinkedList<>();

inorder(list, root);

return list;

}

// recusrivemetho for inorder traversal

private void inorder(List<Integer> list, BSTNode current) {

if (current != null) {

inorder(list, current.getLeft());

list.add(current.getData());

inorder(list, current.getRight());

}

}

//remove from bst

// returns true if deleted, flaseif not found

publicboolean remove(int data) {

boolean removed = remove(data, null, root);

if (size == 0) {

root = null;

}

return removed;

}

//recusrivehleperemthod to remove from a bst

privateboolean remove(int data, BSTNode parent, BSTNode current) {

// if at end

if (current == null) {

return false;

} else {

// compare data to current data

int compare = data – current.getData();

if (compare == 0) { // found

// if no child

if (current.getLeft() == null &&current.getRight() == null) {

if (parent == null) {

root = null;

} else if (parent.getLeft() == current) {

parent.setLeft(null);

} else {

parent.setRight(null);

}

} else if (current.getLeft() != null &&current.getRight() == null) {

if (parent == null) {

root = current.getLeft();

} else if (parent.getLeft() == current) {

parent.setLeft(current.getLeft());

} else {

parent.setRight(current.getLeft());

}

} else if (current.getLeft() == null &&current.getRight() != null) {

if (parent == null) {

root = current.getRight();

} else if (parent.getLeft() == current) {

parent.setLeft(current.getRight());

} else {

parent.setRight(current.getRight());

}

} else {

current.setData(removePredecessor(current));

}

// decrement size

size–;

return true;

} else if (compare < 0) {

// data can be at left

return remove(data, current, current.getLeft());

} else {

// data can be at right

return remove(data, current, current.getRight());

}

}

}

//helper emthod to remove predecessor

privateintremovePredecessor(BSTNode start) {

BSTNode parent = start;

BSTNode current = start.getLeft();

while (current.getRight() != null) {

parent = current;

current = current.getRight();

}

if (parent.getLeft() == current) {

parent.setLeft(current.getLeft());

} else {

parent.setRight(current.getLeft());

}

returncurrent.getData();

}

//find predecessor

public Integer predecessor(int data) {

//get inordee traversal

List<Integer>inorder = inorder();

//find node

int index = inorder.indexOf(data);

//if found and not the first node

if(index > 0 && index <inorder.size())

returninorder.get(index – 1);

else

return null;

}

public Integer successor(int data) {

List<Integer>inorder = inorder();

//find node

int index = inorder.indexOf(data);

// if found and not the last node

if(index >= 0 && index <inorder.size() – 1)

returninorder.get(index + 1);

else

return null;

}

// helper method to find a node in tree

privateBSTNode find(int data, BSTNode current) {

if(current == null)

return null;

else if(current.data == data)

return current;

else if(data <current.data)

return find(data, current.left);

else

return find(data, current.right);

}

//check if a node is present in a bst

publicboolean contains(int data) {

return find(data,root) != null;

}

} 

BSTMain.java

importjava.io.FileNotFoundException;

importjava.io.PrintWriter;

importjava.util.List;

importjava.util.Scanner;

public class BSTMain {

//for inut from console

private static Scanner scanner = new Scanner(System.in);

//for output to file

private static PrintWriterprintWriter;

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

printWriter =  new PrintWriter(“output.txt”);

// create bst

BST bst = new BST();

// populate with initial values

populateBST(bst);

// print traversal

printTraversal(bst.preorder(), “Pre-Order”);

printTraversal(bst.inorder(), “In-Order”);

printTraversal(bst.postorder(), “Post-Order”);

boolean quit = false;

//while user doesnt exit

while(!quit) {

//read command

System.out.print(“Command? “);

String command = scanner.next();

switch (command.toUpperCase()) {

case “I”: //insert

if(scanner.hasNextInt()) {

//add

inttoAdd = scanner.nextInt();

boolean added = bst.add(toAdd);

if(!added) { //not added

System.out.println(toAdd+” already exists, ignore.”);

} else {

printTraversal(bst.inorder(), “In-order”);

}

} else { //if integer not read

System.out.println(“Error: Invalid command”);

}

scanner.nextLine();

break;

case “D”: //delete

if(scanner.hasNextInt()) {

inttoDelete = scanner.nextInt();

boolean deleted = bst.remove(toDelete);

if(!deleted) {

System.out.println(toDelete+”  doesn’t exist!”);

} else {

printTraversal(bst.inorder(), “In-order”);

}

} else {

System.out.println(“Error: Invalid command”);

}

scanner.nextLine();

break;

case “P”: //predecssor

if(scanner.hasNextInt()) {

inttoFind = scanner.nextInt();

if(!bst.contains(toFind)) { // if key not found

System.out.println(toFind+”  doesn’t exist!”);

} else {

//get result

Integer result = bst.predecessor(toFind);

if(result!=null)

System.out.println(result);

else //not found

System.out.println(“Predecessor doesn’t exist!”);

}

} else {

System.out.println(“Error: Invalid command”);

}

scanner.nextLine();

break;

case “S”: //successor

if(scanner.hasNextInt()) {

inttoFind = scanner.nextInt();

if(!bst.contains(toFind)) {

System.out.println(toFind+”  doesn’t exist!”);

} else {

Integer result = bst.successor(toFind);

if(result!=null)

System.out.println(result);

else

System.out.println(“Successor doesn’t exist!”);

}

} else {

System.out.println(“Error: Invalid command”);

}

scanner.nextLine();

break;

case “E”: //exit

quit = true;

printWriter.close();

System.out.println(“Thank you for using my program!”);

break;

case “H”: //help

printHelp();

break;

default: //invalid choice

System.out.println(“Error: Invalid choice”);

scanner.nextLine();

break;

}

}

}

// populate bst with initial values

private static void populateBST(BST bst) {

//read values

System.out.println(“Please enter the initial sequence of values: “);

String[] values = scanner.nextLine().split(” “);

for (int i = 0; i <values.length; i++) {

try{

bst.add(Integer.parseInt(values[i])); //parse and add

} catch(Exception e) {

//if not an intger, ignore

}

}

}

//convert list iofltraversal to a string

private static String traversalToString(List<Integer> traversal) {

String out = “”;

for (int i = 0; i <traversal.size(); i++) {

out += traversal.get(i)+” “;

}

returnout.trim();

}

//print traversal to string and output file

private static void printTraversal(List<Integer> traversal, String type) {

System.out.println(type+”: “+traversalToString(traversal));

printWriter.println(type+”: “+traversalToString(traversal));

}

//print help

private static void printHelp(){

System.out.println(” H Display Help”);

System.out.println(” I Insert a val”);

System.out.println(” D Delete a value”);

System.out.println(” P Find predecessor”);

System.out.println(” S Find successor”);

System.out.println(” E Exit the program”);

}

}