Cover BSTRecursive with tests (TheAlgorithms#4180)

albina-astr · web-flow · commit 3a593d5d3c5d · 2023-05-06T21:10:33.000+03:00
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/BSTRecursive.java b/src/main/java/com/thealgorithms/datastructures/trees/BSTRecursive.java
@@ -1,15 +1,17 @@
 package com.thealgorithms.datastructures.trees;
 
+import com.thealgorithms.datastructures.trees.BinaryTree.Node;
+
 /**
  *
  *
  * <h1>Binary Search Tree (Recursive)</h1>
  *
  * An implementation of BST recursively. In recursive implementation the checks
- * are down the tree First root is checked if not found then its childs are
+ * are down the tree First root is checked if not found then its children are
  * checked 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.
+ * left and right children must themselves be a BST.
  *
  * <p>
  * I have made public functions as methods and to actually implement recursive
@@ -31,30 +33,8 @@ public class BSTRecursive {
         root = null;
     }
 
-    /**
-     * main function for tests
-     */
-    public static void main(String[] args) {
-        BSTRecursive tree = new BSTRecursive();
-        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();
+    public Node getRoot() {
+        return root;
     }
 
     /**
@@ -82,7 +62,7 @@ private Node delete(Node node, int data) {
                 Node temp = node.left;
                 node.left = null;
                 node = temp;
-            } else { // both child are present
+            } else { // both children are present
                 Node temp = node.right;
                 // Find leftmost child of right subtree
                 while (temp.left != null) {
@@ -114,60 +94,6 @@ private Node insert(Node node, int data) {
         return node;
     }
 
-    /**
-     * Recursively print Preorder traversal of the BST
-     *
-     * @param node the root node
-     */
-    private void preOrder(Node 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 travesal of BST.
-     *
-     * @param node the root node
-     */
-    private void postOrder(Node 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 node) {
-        if (node == null) {
-            return;
-        }
-        if (node.left != null) {
-            inOrder(node.left);
-        }
-        System.out.print(node.data + " ");
-        if (node.right != null) {
-            inOrder(node.right);
-        }
-    }
-
     /**
      * Serach recursively if the given value is present in BST or not.
      *
@@ -206,33 +132,6 @@ public void remove(int 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
-    }
-
-    /**
-     * 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 li
-    }
-
-    /**
-     * 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 li
-    }
-
     /**
      * To check if given value is present in tree or not.
      *
@@ -246,23 +145,4 @@ public boolean find(int data) {
         System.out.println(data + " not found.");
         return false;
     }
-
-    /**
-     * The Node class used for building binary search tree
-     */
-    private static class Node {
-
-        int data;
-        Node left;
-        Node right;
-
-        /**
-         * Constructor with data as parameter
-         */
-        Node(int d) {
-            data = d;
-            left = null;
-            right = null;
-        }
-    }
 }
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/BSTRecursiveTest.java b/src/test/java/com/thealgorithms/datastructures/trees/BSTRecursiveTest.java
@@ -0,0 +1,61 @@
+package com.thealgorithms.datastructures.trees;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+/**
+ * @author Albina Gimaletdinova on 06/05/2023
+ */
+public class BSTRecursiveTest {
+    @Test
+    public void testBSTIsCorrectlyConstructedFromOneNode() {
+        BSTRecursive tree = new BSTRecursive();
+        tree.add(6);
+
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
+    }
+
+    @Test
+    public void testBSTIsCorrectlyCleanedAndEmpty() {
+        BSTRecursive tree = new BSTRecursive();
+
+        tree.add(6);
+        tree.remove(6);
+
+        tree.add(12);
+        tree.add(1);
+        tree.add(2);
+
+        tree.remove(1);
+        tree.remove(2);
+        tree.remove(12);
+
+        Assertions.assertNull(tree.getRoot());
+    }
+
+    @Test
+    public void testBSTIsCorrectlyCleanedAndNonEmpty() {
+        BSTRecursive tree = new BSTRecursive();
+
+        tree.add(6);
+        tree.remove(6);
+
+        tree.add(12);
+        tree.add(1);
+        tree.add(2);
+
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
+    }
+
+    @Test
+    public void testBSTIsCorrectlyConstructedFromMultipleNodes() {
+        BSTRecursive tree = new BSTRecursive();
+        tree.add(7);
+        tree.add(1);
+        tree.add(5);
+        tree.add(100);
+        tree.add(50);
+
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
+    }
+}
