Skip to content

BSTRecursive refactoring: #4180

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
May 6, 2023
Merged

BSTRecursive refactoring: #4180

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
134 changes: 7 additions & 127 deletions src/main/java/com/thealgorithms/datastructures/trees/BSTRecursive.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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
Expand All @@ -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;
}

/**
Expand Down Expand Up @@ -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) {
Expand Down Expand Up @@ -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.
*
Expand Down Expand Up @@ -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.
*
Expand All @@ -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;
}
}
}
61 changes: 61 additions & 0 deletions src/test/java/com/thealgorithms/datastructures/trees/BSTRecursiveTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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()));
}
}