Who says Java does not supports pointers part-seven, lets implement a "Binary Search Tree" in Java, a code by Pankaj

This awesome code of "Binary Search Tree"
(BST) is implemented and provided by Pankaj
,from Nit-Arunachal Pradesh

Note: A Binary Search Tree is a non linear data
structure. It provides a very fast store and

retrieve operation for further information on

BST please click on given link

know more about Binary Search Tree

Note: Please create a "Java Project" inside

Eclipse before using this code

## save this class inside BSTNode.java file ## import java.util.Scanner; // Class BSTNode class BSTNode { BSTNode left, right; String data; // Constructor to create node public BSTNode() { left = null; right = null; data = null; } // Constructor to provide data to node public BSTNode(String n) { left = null; right = null; data = n; } // Method to set left node public void setLeft(BSTNode n) { left = n; } // Method to set right node public void setRight(BSTNode n) { right = n; } // Method to get left node public BSTNode getLeft() { return left; } // Method to get right node public BSTNode getRight() { return right; } // Method to provide data to node public void setData(String d) { data = d; } // Method to get data to node public String getData() { return data; } }

## save this class inside BST.java file ## // Class BST class BST { private BSTNode root; public BST() { root = null; } // empty check public boolean isEmpty() { return root == null; } // insert data public void insert(String data) { root = insert(root, data); } private BSTNode insert(BSTNode node, String data) { if (node == null) node = new BSTNode(data); else { int temp=data.compareTo(node.getData()); if (temp<0) node.left = insert(node.left, data); else node.right = insert(node.right, data); } return node; } //delete data public void delete(String k) { if (isEmpty()) System.out.println("Tree Empty"); else if (search(k) == false) System.out.println("Sorry "+ k +" is not present"); else { root = delete(root, k); System.out.println(k+ " deleted from the tree"); } } private BSTNode delete(BSTNode root, String k) { BSTNode p, p2, n; if ((root.getData()).equalsIgnoreCase(k)) { BSTNode lt, rt; lt = root.getLeft(); rt = root.getRight(); if (lt == null && rt == null) return null; else if (lt == null) { p = rt; return p; } else if (rt == null) { p = lt; return p; } else { p2 = rt; p = rt; while (p.getLeft() != null) p = p.getLeft(); p.setLeft(lt); return p2; } } //Edit here if (k.compareTo(root.getData())<0) { n = delete(root.getLeft(), k); root.setLeft(n); } else { n = delete(root.getRight(), k); root.setRight(n); } return root; } // number of nodes public int countNodes() { return countNodes(root); } private int countNodes(BSTNode r) { if (r == null) return 0; else { int l = 1; l += countNodes(r.getLeft()); l += countNodes(r.getRight()); return l; } } // search an element public boolean search(String val) { return search(root, val); } private boolean search(BSTNode r, String val) { boolean found = false; while ((r != null) && !found) { String rval = r.getData(); //edit here if (val.compareTo(rval)<0) r = r.getLeft(); else if (val.compareTo(rval)>0) r = r.getRight(); else { found = true; break; } found = search(r, val); } return found; } //inorder traversal public void inorder() { inorder(root); } private void inorder(BSTNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() +" "); inorder(r.getRight()); } } // preorder traversal public void preorder() { preorder(root); } private void preorder(BSTNode r) { if (r != null) { System.out.print(r.getData() +" "); preorder(r.getLeft()); preorder(r.getRight()); } } // postorder traversal public void postorder() { postorder(root); } private void postorder(BSTNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() +" "); } } }
## save this class inside BinarySearchTree.java
file ## // main Class BinarySearchTree public class BinarySearchTree { public static void main(String[] args) { Scanner scan = new Scanner(System.in); BST bst = new BST(); System.out.println("Binary Search Tree Test\n"); char ch; do { System.out.println("\nBinary Search Tree Operations\n"); System.out.println("1. insert "); System.out.println("2. delete"); System.out.println("3. search"); System.out.println("4. count nodes"); System.out.println("5. check empty"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter String to insert"); bst.insert( scan.next() ); break; case 2 : System.out.println("Enter String element to delete"); bst.delete( scan.next() ); break; case 3 : System.out.println("Enter String element to search"); System.out.println("Search result : "+ bst.search( scan.next() )); break; case 4 : System.out.println("Nodes = "+ bst.countNodes()); break; case 5 : System.out.println("Empty status = "+ bst.isEmpty()); break; default : System.out.println("Wrong Entry \n "); break; } System.out.print("\nPost order : "); bst.postorder(); System.out.print("\nPre order : "); bst.preorder(); System.out.print("\nIn order : "); bst.inorder(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }