Implementation of Binary Search Tree in Java

This document provides a step-by-step guide on how to implement a Binary Search Tree in Java. It includes the code for creating a BST, methods for inserting and deleting nodes, and displaying the tree. The document also includes outputs of the program.

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

12IMPLEMENTATION OF BINARY SEARCH TREE IN JAVA