Skip to content

BSTIterative refactoring #4164

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
Apr 24, 2023
Merged

BSTIterative refactoring #4164

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
128 changes: 4 additions & 124 deletions src/main/java/com/thealgorithms/datastructures/trees/BSTIterative.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,7 @@
package com.thealgorithms.datastructures.trees;

import com.thealgorithms.datastructures.trees.BinaryTree.Node;

/**
*
*
Expand All @@ -13,7 +15,6 @@
*
* @author [Lakhan Nad](https://github.com/Lakhan-Nad)
*/
import java.util.Stack;

public class BSTIterative {

Expand All @@ -29,30 +30,8 @@ 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();
public Node getRoot() {
return root;
}

/**
Expand Down Expand Up @@ -184,86 +163,6 @@ public void remove(int data) {
}
}

/**
* A method for inorder traversal of BST.
*/
public void inorder() {
if (this.root == null) {
System.out.println("This BST is empty.");
return;
}
System.out.println("Inorder traversal of this tree is:");
Stack<Node> st = new Stack<Node>();
Node cur = this.root;
while (cur != null || !st.empty()) {
while (cur != null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
System.out.print(cur.data + " ");
cur = cur.right;
}
System.out.println(); // for next line
}

/**
* A method used to print postorder traversal of BST.
*/
public void postorder() {
if (this.root == null) {
System.out.println("This BST is empty.");
return;
}
System.out.println("Postorder traversal of this tree is:");
Stack<Node> st = new Stack<Node>();
Node cur = this.root, temp2;
while (cur != null || !st.empty()) {
if (cur != null) {
st.push(cur);
cur = cur.left;
} else {
temp2 = st.peek();
if (temp2.right != null) {
cur = temp2.right;
} else {
st.pop();
while (!st.empty() && st.peek().right == temp2) {
System.out.print(temp2.data + " ");
temp2 = st.pop();
}
System.out.print(temp2.data + " ");
}
}
}
System.out.println(); // for next line
}

/**
* Method used to display preorder traversal of BST.
*/
public void preorder() {
if (this.root == null) {
System.out.println("This BST is empty.");
return;
}
System.out.println("Preorder traversal of this tree is:");
Stack<Node> st = new Stack<Node>();
st.push(this.root);
Node temp;
while (!st.empty()) {
temp = st.pop();
System.out.print(temp.data + " ");
if (temp.right != null) {
st.push(temp.right);
}
if (temp.left != null) {
st.push(temp.left);
}
}
System.out.println(); // for next line
}

/**
* A method to check if given data exists in out Binary Search Tree.
*
Expand All @@ -289,23 +188,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/BSTIterativeTest.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 23/04/2023
*/
public class BSTIterativeTest {
@Test
public void testBSTIsCorrectlyConstructedFromOneNode() {
BSTIterative tree = new BSTIterative();
tree.add(6);

Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
}

@Test
public void testBSTIsCorrectlyCleanedAndEmpty() {
BSTIterative tree = new BSTIterative();

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() {
BSTIterative tree = new BSTIterative();

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() {
BSTIterative tree = new BSTIterative();
tree.add(7);
tree.add(1);
tree.add(5);
tree.add(100);
tree.add(50);

Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
}
}