BST Recursive Generic
d
package com.thealgorithms.datastructures.trees;
import java.util.ArrayList;
import java.util.List;
/**
* <h1>Binary Search Tree (Recursive) Generic Type Implementation</h1>
*
* <p>
* A recursive implementation of generic type BST.
*
* Reference: <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Wiki links for BST</a>
* </p>
*
* @author [Madhur Panwar](<a href="https://github.com/mdrpanwar">git-Madhur Panwar</a>)
*/
public class BSTRecursiveGeneric<T extends Comparable<T>> {
/**
* only data member is root of BST
*/
private Node<T> root;
/**
* Constructor use to initialize node as null
*/
public BSTRecursiveGeneric() {
root = null;
}
/**
* main function for testing
*/
public static void main(String[] args) {
System.out.println("Testing for integer data...");
// Integer
BSTRecursiveGeneric<Integer> integerTree = new BSTRecursiveGeneric<Integer>();
integerTree.add(5);
integerTree.add(10);
integerTree.add(9);
assert !integerTree.find(4)
: "4 is not yet present in BST";
assert integerTree.find(10)
: "10 should be present in BST";
integerTree.remove(9);
assert !integerTree.find(9)
: "9 was just deleted from BST";
integerTree.remove(1);
assert !integerTree.find(1)
: "Since 1 was not present so find deleting would do no change";
integerTree.add(20);
integerTree.add(70);
assert integerTree.find(70)
: "70 was inserted but not found";
/*
Will print in following order
5 10 20 70
*/
integerTree.inorder();
System.out.println();
System.out.println("Testing for string data...");
// String
BSTRecursiveGeneric<String> stringTree = new BSTRecursiveGeneric<String>();
stringTree.add("banana");
stringTree.add("pineapple");
stringTree.add("date");
assert !stringTree.find("girl")
: "girl is not yet present in BST";
assert stringTree.find("pineapple")
: "10 should be present in BST";
stringTree.remove("date");
assert !stringTree.find("date")
: "date was just deleted from BST";
stringTree.remove("boy");
assert !stringTree.find("boy")
: "Since boy was not present so deleting would do no change";
stringTree.add("india");
stringTree.add("hills");
assert stringTree.find("hills")
: "hills was inserted but not found";
/*
Will print in following order
banana hills india pineapple
*/
stringTree.inorder();
}
/**
* Recursive method to delete a data if present in BST.
*
* @param node the node under which to (recursively) search for data
* @param data the value to be deleted
* @return Node the updated value of root parameter after delete operation
*/
private Node<T> delete(Node<T> node, T data) {
if (node == null) {
System.out.println("No such data present in BST.");
} else if (node.data.compareTo(data) > 0) {
node.left = delete(node.left, data);
} else if (node.data.compareTo(data) < 0) {
node.right = delete(node.right, data);
} else {
if (node.right == null && node.left == null) { // If it is leaf node
node = null;
} else if (node.left == null) { // If only right node is present
Node<T> temp = node.right;
node.right = null;
node = temp;
} else if (node.right == null) { // Only left node is present
Node<T> temp = node.left;
node.left = null;
node = temp;
} else { // both child are present
Node<T> temp = node.right;
// Find leftmost child of right subtree
while (temp.left != null) {
temp = temp.left;
}
node.data = temp.data;
node.right = delete(node.right, temp.data);
}
}
return node;
}
/**
* Recursive insertion of value in BST.
*
* @param node to check if the data can be inserted in current node or its
* subtree
* @param data the value to be inserted
* @return the modified value of the root parameter after insertion
*/
private Node<T> insert(Node<T> node, T data) {
if (node == null) {
node = new Node<>(data);
} else if (node.data.compareTo(data) > 0) {
node.left = insert(node.left, data);
} else if (node.data.compareTo(data) < 0) {
node.right = insert(node.right, data);
}
return node;
}
/**
* Recursively print Preorder traversal of the BST
*
* @param node the root node
*/
private void preOrder(Node<T> node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
if (node.left != null) {
preOrder(node.left);
}
if (node.right != null) {
preOrder(node.right);
}
}
/**
* Recursively print Postorder traversal of BST.
*
* @param node the root node
*/
private void postOrder(Node<T> node) {
if (node == null) {
return;
}
if (node.left != null) {
postOrder(node.left);
}
if (node.right != null) {
postOrder(node.right);
}
System.out.print(node.data + " ");
}
/**
* Recursively print Inorder traversal of BST.
*
* @param node the root node
*/
private void inOrder(Node<T> node) {
if (node == null) {
return;
}
if (node.left != null) {
inOrder(node.left);
}
System.out.print(node.data + " ");
if (node.right != null) {
inOrder(node.right);
}
}
/**
* Recursively traverse the tree using inorder traversal and keep adding
* elements to argument list.
*
* @param node the root node
* @param sortedList the list to add the srted elements into
*/
private void inOrderSort(Node<T> node, List<T> sortedList) {
if (node == null) {
return;
}
if (node.left != null) {
inOrderSort(node.left, sortedList);
}
sortedList.add(node.data);
if (node.right != null) {
inOrderSort(node.right, sortedList);
}
}
/**
* Search recursively if the given value is present in BST or not.
*
* @param node the node under which to check
* @param data the value to be checked
* @return boolean if data is present or not
*/
private boolean search(Node<T> node, T data) {
if (node == null) {
return false;
} else if (node.data.compareTo(data) == 0) {
return true;
} else if (node.data.compareTo(data) > 0) {
return search(node.left, data);
} else {
return search(node.right, data);
}
}
/**
* add in BST. if the value is not already present it is inserted or else no
* change takes place.
*
* @param data the value to be inserted
*/
public void add(T data) {
this.root = insert(this.root, data);
}
/**
* If data is present in BST delete it else do nothing.
*
* @param data the value to be removed
*/
public void remove(T data) {
this.root = delete(this.root, data);
}
/**
* To call inorder traversal on tree
*/
public void inorder() {
System.out.println("Inorder traversal of this tree is:");
inOrder(this.root);
System.out.println(); // for next line
}
/**
* return a sorted list by traversing the tree elements using inorder
* traversal
*/
public List<T> inorderSort() {
List<T> sortedList = new ArrayList<>();
inOrderSort(this.root, sortedList);
return sortedList;
}
/**
* To call postorder traversal on tree
*/
public void postorder() {
System.out.println("Postorder traversal of this tree is:");
postOrder(this.root);
System.out.println(); // for next line
}
/**
* To call preorder traversal on tree.
*/
public void preorder() {
System.out.println("Preorder traversal of this tree is:");
preOrder(this.root);
System.out.println(); // for next line
}
/**
* To check if given value is present in tree or not.
*
* @param data the data to be found for
*/
public boolean find(T data) {
if (search(this.root, data)) {
System.out.println(data + " is present in given BST.");
return true;
}
System.out.println(data + " not found.");
return false;
}
/**
* The generic Node class used for building binary search tree
*/
private static class Node<T> {
T data;
Node<T> left;
Node<T> right;
/**
* Constructor with data as parameter
*/
Node(T d) {
data = d;
left = null;
right = null;
}
}
}
