York University ITEC 2620 Assignment 2: Binary Search Tree in Java

This document presents a complete Java implementation of a Binary Search Tree (BST) as a solution to an assignment for York University's ITEC 2620 course. The code includes the essential methods for BST functionality, such as inserting and deleting nodes, and a method called oneChildMax to determine a specific property of the tree. The provided code includes the BST.java file which defines the class BST, implementing the insert and delete methods, along with the oneChildMax method to check for nodes having at most one child. The code also defines the BSTNode class and the Tree interface. The implementation adheres to the assignment's requirements, providing a functional and well-structured solution. The included code provides a practical example for students studying data structures and algorithms, specifically binary search trees.

Running Head: IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
Name of the Student:
Name of the University:
Author Note:

1IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
Table of Contents
The java code of BST.java...............................................................................................................2
Outputs of the program..................................................................................................................10

2IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
The java code of BST.java
public class BST implements Tree
{
//================
// variables
//================
// Tree Root
private BSTNode root;
//================
// Constructors
//================
// Create an empty Binary search Tree with a Root set to null
public BST()
{
root = null;
}
//================
// Methods

3IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
//================
// Print the Binary search Tree
public void display()
{
System.out.print("( ");
traverse(root);
System.out.println(" )");
}
// A recursive function that traverses and prints out
// the binary search tree with an inorder traversal.
private void traverse(BSTNode node)
{
if (node == null)
return;
traverse(node.left);
System.out.print(node.val +" ");
traverse(node.right);

4IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
}
//================
// Implement These
//================
// This method takes an integer parameter n and inserts it
// as a node in a binary search tree.
public void insert(int n)
{
// TODO: Implement the insert function of
// the Binary Search Tree
root = insert(root, n);
return;
}
private BSTNode insert(BSTNode node, int val)
{
if (node == null)
{

5IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
node = new BSTNode(val);
}
else
{
if (val <= node.val)
node.left = insert(node.left, val);
else
node.right = insert(node.right, val);
}
return node;
}
// This method searches the binary tree for an integer n
// and if it exists deletes this node from the tree.
public void delete(int n)
{
// TODO: Implement the delete function of
// the Binary search Tree
if( root == null){

6IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
System.out.println("Tree is Empty.\n");
}
else {
root = delete(root, n);
}
return;
}
//implementing the recursive delete function
private BSTNode delete(BSTNode node, int val){
if(node == null){
return node; //if the tree is empty
}
// search the tree for the value
if(val < node.val)
node.left = delete(node.left, val);
else if(val> node.val)
node.right = delete(node.right, val);

7IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
// if the value is same as root value then this node should be deleted
else
{
// if the tree contains only one child or no child
if (node.right == null)
return node.left;
else if (node.left == null)
return node.right;
// if the node has two children then get the inorder successor
node.val = minValue(node.right);
// Deleting the inorder successor
node.right = delete(node.right, node.val);
}
return node;
}
int minValue(BSTNode node){

8IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
int mvalue = node.val;
while(node.left != null)
{
mvalue = node.left.val;
node = node.left;
}
return mvalue;
}
// This function returns true if no node in the binary tree
// has more than child, otherwise it returns false.
public boolean onechildMax(int t1[], int size)
{
// TODO: Implement the onechildMax function of
// the Binary search Tree
int nextSuccessor, lastSuccessor;

9IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
for(int i = 0;i < size - 1;i++){
nextSuccessor = t1[i] - t1[i+1];
lastSuccessor = t1[i] - t1[size - 1];
if(nextSuccessor * lastSuccessor < 0){
return false;
};
}
return true;
}
}
//End of class BST

10IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA
Outputs of the program

11IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA