Skip to content

Commit f69cd7c

Browse files
albina-astralbina-astr
authored
Remove redundant code and add tests for BSTIterative (TheAlgorithms#4164)
1 parent 4c18e60 commit f69cd7c

File tree

2 files changed

+65
-124
lines changed

2 files changed

+65
-124
lines changed

‎src/main/java/com/thealgorithms/datastructures/trees/BSTIterative.java

Lines changed: 4 additions & 124 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package com.thealgorithms.datastructures.trees;
22

3+
import com.thealgorithms.datastructures.trees.BinaryTree.Node;
4+
35
/**
46
*
57
*
@@ -13,7 +15,6 @@
1315
*
1416
* @author [Lakhan Nad](https://github.com/Lakhan-Nad)
1517
*/
16-
import java.util.Stack;
1718

1819
public class BSTIterative {
1920

@@ -29,30 +30,8 @@ public class BSTIterative {
2930
root = null;
3031
}
3132

32-
/**
33-
* main function for tests
34-
*/
35-
public static void main(String[] args) {
36-
BSTIterative tree = new BSTIterative();
37-
tree.add(3);
38-
tree.add(2);
39-
tree.add(9);
40-
assert !tree.find(4) : "4 is not yet present in BST";
41-
assert tree.find(2) : "2 should be present in BST";
42-
tree.remove(2);
43-
assert !tree.find(2) : "2 was just deleted from BST";
44-
tree.remove(1);
45-
assert !tree.find(
46-
1
47-
) : "Since 1 was not present so find deleting would do no change";
48-
tree.add(30);
49-
tree.add(40);
50-
assert tree.find(40) : "40 was inserted but not found";
51-
/*
52-
Will print following order
53-
3 9 30 40
54-
*/
55-
tree.inorder();
33+
public Node getRoot() {
34+
return root;
5635
}
5736

5837
/**
@@ -184,86 +163,6 @@ public void remove(int data) {
184163
}
185164
}
186165

187-
/**
188-
* A method for inorder traversal of BST.
189-
*/
190-
public void inorder() {
191-
if (this.root == null) {
192-
System.out.println("This BST is empty.");
193-
return;
194-
}
195-
System.out.println("Inorder traversal of this tree is:");
196-
Stack<Node> st = new Stack<Node>();
197-
Node cur = this.root;
198-
while (cur != null || !st.empty()) {
199-
while (cur != null) {
200-
st.push(cur);
201-
cur = cur.left;
202-
}
203-
cur = st.pop();
204-
System.out.print(cur.data + " ");
205-
cur = cur.right;
206-
}
207-
System.out.println(); // for next line
208-
}
209-
210-
/**
211-
* A method used to print postorder traversal of BST.
212-
*/
213-
public void postorder() {
214-
if (this.root == null) {
215-
System.out.println("This BST is empty.");
216-
return;
217-
}
218-
System.out.println("Postorder traversal of this tree is:");
219-
Stack<Node> st = new Stack<Node>();
220-
Node cur = this.root, temp2;
221-
while (cur != null || !st.empty()) {
222-
if (cur != null) {
223-
st.push(cur);
224-
cur = cur.left;
225-
} else {
226-
temp2 = st.peek();
227-
if (temp2.right != null) {
228-
cur = temp2.right;
229-
} else {
230-
st.pop();
231-
while (!st.empty() && st.peek().right == temp2) {
232-
System.out.print(temp2.data + " ");
233-
temp2 = st.pop();
234-
}
235-
System.out.print(temp2.data + " ");
236-
}
237-
}
238-
}
239-
System.out.println(); // for next line
240-
}
241-
242-
/**
243-
* Method used to display preorder traversal of BST.
244-
*/
245-
public void preorder() {
246-
if (this.root == null) {
247-
System.out.println("This BST is empty.");
248-
return;
249-
}
250-
System.out.println("Preorder traversal of this tree is:");
251-
Stack<Node> st = new Stack<Node>();
252-
st.push(this.root);
253-
Node temp;
254-
while (!st.empty()) {
255-
temp = st.pop();
256-
System.out.print(temp.data + " ");
257-
if (temp.right != null) {
258-
st.push(temp.right);
259-
}
260-
if (temp.left != null) {
261-
st.push(temp.left);
262-
}
263-
}
264-
System.out.println(); // for next line
265-
}
266-
267166
/**
268167
* A method to check if given data exists in out Binary Search Tree.
269168
*
@@ -289,23 +188,4 @@ public boolean find(int data) {
289188
System.out.println(data + " not found.");
290189
return false;
291190
}
292-
293-
/**
294-
* The Node class used for building binary search tree
295-
*/
296-
private static class Node {
297-
298-
int data;
299-
Node left;
300-
Node right;
301-
302-
/**
303-
* Constructor with data as parameter
304-
*/
305-
Node(int d) {
306-
data = d;
307-
left = null;
308-
right = null;
309-
}
310-
}
311191
}

‎src/test/java/com/thealgorithms/datastructures/trees/BSTIterativeTest.java

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.thealgorithms.datastructures.trees;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.api.Test;
5+
6+
/**
7+
* @author Albina Gimaletdinova on 23/04/2023
8+
*/
9+
public class BSTIterativeTest {
10+
@Test
11+
public void testBSTIsCorrectlyConstructedFromOneNode() {
12+
BSTIterative tree = new BSTIterative();
13+
tree.add(6);
14+
15+
Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
16+
}
17+
18+
@Test
19+
public void testBSTIsCorrectlyCleanedAndEmpty() {
20+
BSTIterative tree = new BSTIterative();
21+
22+
tree.add(6);
23+
tree.remove(6);
24+
25+
tree.add(12);
26+
tree.add(1);
27+
tree.add(2);
28+
29+
tree.remove(1);
30+
tree.remove(2);
31+
tree.remove(12);
32+
33+
Assertions.assertNull(tree.getRoot());
34+
}
35+
36+
@Test
37+
public void testBSTIsCorrectlyCleanedAndNonEmpty() {
38+
BSTIterative tree = new BSTIterative();
39+
40+
tree.add(6);
41+
tree.remove(6);
42+
43+
tree.add(12);
44+
tree.add(1);
45+
tree.add(2);
46+
47+
Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
48+
}
49+
50+
@Test
51+
public void testBSTIsCorrectlyConstructedFromMultipleNodes() {
52+
BSTIterative tree = new BSTIterative();
53+
tree.add(7);
54+
tree.add(1);
55+
tree.add(5);
56+
tree.add(100);
57+
tree.add(50);
58+
59+
Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(tree.getRoot()));
60+
}
61+
}

0 commit comments

Comments
 (0)