Tests added for BST DataStructures

Lakhan-Nad · Lakhan-Nad · commit 75480d44bf43 · 2020-08-18T21:03:31.000+05:30
diff --git a/DataStructures/Trees/BSTIterative.java b/DataStructures/Trees/BSTIterative.java
@@ -3,9 +3,9 @@
  *
  * <h1>Binary Search Tree (Iterative)</h1>
  *
- * An implementation of BST iteratively. Binary Search Tree is a binary tree which satisfies three
- * properties: left child is less than root node, right child is grater than root node, both left
- * and right childs must themselves be a BST.
+ * <p>An implementation of BST iteratively. Binary Search Tree is a binary tree which satisfies
+ * three properties: left child is less than root node, right child is grater than root node, both
+ * left and right childs must themselves be a BST.
  *
  * @author [Lakhan Nad](https://github.com/Lakhan-Nad)
  */
@@ -20,6 +20,28 @@ public class BSTIterative {
     root = null;
   }
 
+  /** main function for tests */
+  public static void main(String[] args) {
+    BSTIterative tree = new BSTIterative();
+    tree.add(3);
+    tree.add(2);
+    tree.add(9);
+    assert !tree.find(4) : "4 is not yet present in BST";
+    assert tree.find(2) : "2 should be present in BST";
+    tree.remove(2);
+    assert !tree.find(2) : "2 was just deleted from BST";
+    tree.remove(1);
+    assert !tree.find(1) : "Since 1 was not present so find deleting would do no change";
+    tree.add(30);
+    tree.add(40);
+    assert tree.find(40) : "40 was inserted but not found";
+    /*
+       Will print following order
+       3 9 30 40
+    */
+    tree.inorder();
+  }
+
   /**
    * A method to insert a new value in BST. If the given value is already present in BST the
    * insertion is ignored.
@@ -47,24 +69,24 @@ public void add(int data) {
         return; // if data already present we ignore insertion
       }
     }
-    /* Creates a newnode with the value passed
+    /* Creates a newNode with the value passed
      * Since this data doesn't already exists
      */
-    Node newnode = new Node(data);
+    Node newNode = new Node(data);
     /* If the parent node is null
      * then the insertion is to be done in
      * root itself.
      */
     if (parent == null) {
-      this.root = newnode;
+      this.root = newNode;
     } else {
       /* Check if insertion is to be made in
        * left or right subtree.
        */
       if (rightOrLeft == 0) {
-        parent.left = newnode;
+        parent.left = newNode;
       } else {
-        parent.right = newnode;
+        parent.right = newNode;
       }
     }
   }
@@ -250,7 +272,7 @@ public boolean find(int data) {
   }
 
   /** The Node class used for building binary search tree */
-  private class Node {
+  private static class Node {
     int data;
     Node left;
     Node right;
diff --git a/DataStructures/Trees/BSTRecursive.java b/DataStructures/Trees/BSTRecursive.java
@@ -16,137 +16,160 @@
 public class BSTRecursive {
   /** only data member is root of BST */
   private Node root;
+
   /** Constructor use to initialize node as null */
   BSTRecursive() {
     root = null;
   }
 
+  /** main function for tests */
+  public static void main(String[] args) {
+    BSTIterative tree = new BSTIterative();
+    tree.add(5);
+    tree.add(10);
+    tree.add(9);
+    assert !tree.find(4) : "4 is not yet present in BST";
+    assert tree.find(10) : "10 should be present in BST";
+    tree.remove(9);
+    assert !tree.find(9) : "9 was just deleted from BST";
+    tree.remove(1);
+    assert !tree.find(1) : "Since 1 was not present so find deleting would do no change";
+    tree.add(20);
+    tree.add(70);
+    assert tree.find(70) : "70 was inserted but not found";
+    /*
+     Will print in following order
+     5 10 20 70
+    */
+    tree.inorder();
+  }
+
   /**
    * Recursive method to delete a data if present in BST.
    *
-   * @param root the current node to search for data
+   * @param node the current node to search for data
    * @param data the value to be deleted
    * @return Node the updated value of root parameter after delete operation
    */
-  private Node delete(Node root, int data) {
-    if (root == null) {
+  private Node delete(Node node, int data) {
+    if (node == null) {
       System.out.println("No such data present in BST.");
-    } else if (root.data > data) {
-      root.left = delete(root.left, data);
-    } else if (root.data < data) {
-      root.right = delete(root.right, data);
+    } else if (node.data > data) {
+      node.left = delete(node.left, data);
+    } else if (node.data < data) {
+      node.right = delete(node.right, data);
     } else {
-      if (root.right == null && root.left == null) { // If it is leaf node
-        root = null;
-      } else if (root.left == null) { // If only right node is present
-        Node temp = root.right;
-        root.right = null;
-        root = temp;
-      } else if (root.right == null) { // Only left node is present
-        Node temp = root.left;
-        root.left = null;
-        root = temp;
+      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 temp = node.right;
+        node.right = null;
+        node = temp;
+      } else if (node.right == null) { // Only left node is present
+        Node temp = node.left;
+        node.left = null;
+        node = temp;
       } else { // both child are present
-        Node temp = root.right;
+        Node temp = node.right;
         // Find leftmost child of right subtree
         while (temp.left != null) {
           temp = temp.left;
         }
-        root.data = temp.data;
-        root.right = delete(root.right, temp.data);
+        node.data = temp.data;
+        node.right = delete(node.right, temp.data);
       }
     }
-    return root;
+    return node;
   }
 
   /**
    * Recursive insertion of value in BST.
    *
-   * @param root to check if the data can be inserted in current node or its subtree
+   * @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 insert(Node root, int data) {
-    if (root == null) {
-      root = new Node(data);
-    } else if (root.data > data) {
-      root.left = insert(root.left, data);
-    } else if (root.data < data) {
-      root.right = insert(root.right, data);
+  private Node insert(Node node, int data) {
+    if (node == null) {
+      node = new Node(data);
+    } else if (node.data > data) {
+      node.left = insert(node.left, data);
+    } else if (node.data < data) {
+      node.right = insert(node.right, data);
     }
-    return root;
+    return node;
   }
 
   /**
    * Recursively print Preorder traversal of the BST
    *
-   * @param root
+   * @param node the root node
    */
-  private void preOrder(Node root) {
-    if (root == null) {
+  private void preOrder(Node node) {
+    if (node == null) {
       return;
     }
-    System.out.print(root.data + " ");
-    if (root.left != null) {
-      preOrder(root.left);
+    System.out.print(node.data + " ");
+    if (node.left != null) {
+      preOrder(node.left);
     }
-    if (root.right != null) {
-      preOrder(root.right);
+    if (node.right != null) {
+      preOrder(node.right);
     }
   }
 
   /**
    * Recursively print Postorder travesal of BST.
    *
-   * @param root
+   * @param node the root node
    */
-  private void postOrder(Node root) {
-    if (root == null) {
+  private void postOrder(Node node) {
+    if (node == null) {
       return;
     }
-    if (root.left != null) {
-      postOrder(root.left);
+    if (node.left != null) {
+      postOrder(node.left);
     }
-    if (root.right != null) {
-      postOrder(root.right);
+    if (node.right != null) {
+      postOrder(node.right);
     }
-    System.out.print(root.data + " ");
+    System.out.print(node.data + " ");
   }
 
   /**
    * Recursively print Inorder traversal of BST.
    *
-   * @param root
+   * @param node the root node
    */
-  private void inOrder(Node root) {
-    if (root == null) {
+  private void inOrder(Node node) {
+    if (node == null) {
       return;
     }
-    if (root.left != null) {
-      inOrder(root.left);
+    if (node.left != null) {
+      inOrder(node.left);
     }
-    System.out.print(root.data + " ");
-    if (root.right != null) {
-      inOrder(root.right);
+    System.out.print(node.data + " ");
+    if (node.right != null) {
+      inOrder(node.right);
     }
   }
 
   /**
    * Serach recursively if the given value is present in BST or not.
    *
-   * @param root the current node to check
+   * @param node the current node to check
    * @param data the value to be checked
    * @return boolean if data is present or not
    */
-  private boolean search(Node root, int data) {
-    if (root == null) {
+  private boolean search(Node node, int data) {
+    if (node == null) {
       return false;
-    } else if (root.data == data) {
+    } else if (node.data == data) {
       return true;
-    } else if (root.data > data) {
-      return search(root.left, data);
+    } else if (node.data > data) {
+      return search(node.left, data);
     } else {
-      return search(root.right, data);
+      return search(node.right, data);
     }
   }
 
@@ -192,9 +215,9 @@ public void preorder() {
   /**
    * To check if given value is present in tree or not.
    *
-   * @param data
+   * @param data the data to be found for
    */
-  public void find(int data) {
+  public boolean find(int data) {
     if (search(this.root, data)) {
       System.out.println(data + " is present in given BST.");
       return true;
@@ -204,7 +227,7 @@ public void find(int data) {
   }
 
   /** The Node class used for building binary search tree */
-  private class Node {
+  private static class Node {
     int data;
     Node left;
     Node right;
