BSTRecursiveGeneric.java

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>)
 * @author [Udaya Krishnan M](<a href="https://github.com/UdayaKrishnanM/">git-Udaya Krishnan M</a>) {added prettyDisplay() method}
 */
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;
 }

 /**
 * Displays the tree is a structured format
 */
 public void prettyDisplay() {
 prettyDisplay(root, 0);
 }

 private void prettyDisplay(Node<T> node, int level) {
 if (node == null) {
 return;
 }
 prettyDisplay(node.right, level + 1);
 if (level != 0) {
 for (int i = 0; i < level - 1; i++) {
 System.out.print("|\t");
 }
 System.out.println("|---->" + node.data);
 } else {
 System.out.println(node.data);
 }
 prettyDisplay(node.left, level + 1);
 }

 /**
 * 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);
 integerTree.add(4);
 integerTree.add(3);
 integerTree.add(1);
 System.out.println("Pretty Display of current tree is:");
 integerTree.prettyDisplay();
 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
 */
 System.out.println("Pretty Display of current tree is:");
 integerTree.prettyDisplay();
 integerTree.inorder();
 System.out.println("Pretty Display of current tree is:");
 integerTree.prettyDisplay();
 System.out.println();
 System.out.println("Testing for string data...");
 // String
 BSTRecursiveGeneric<String> stringTree = new BSTRecursiveGeneric<String>();

 stringTree.add("banana");
 stringTree.add("apple");
 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";
 System.out.println("Pretty Display of current tree is:");
 stringTree.prettyDisplay();
 /*
 Will print in following order
 banana hills india pineapple
 */
 stringTree.inorder();
 System.out.println("Pretty Display of current tree is:");
 stringTree.prettyDisplay();
 }

 /**
 * 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;
 }
 }
}