Skip to content

Commit efdd1dd

Browse files
Lakhan-NadLakhan-Nad
committed
DS: Binary Search Tree added Closes TheAlgorithms#1420 
1 parent ee11fca commit efdd1dd

File tree

2 files changed

+484
-0
lines changed

2 files changed

+484
-0
lines changed

‎DataStructures/Trees/BSTIterative.java‎

Lines changed: 265 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,265 @@
1+
/**
2+
*
3+
*
4+
* <h1>Binary Search Tree (Iterative)</h1>
5+
*
6+
* An implementation of BST iteratively. Binary Search Tree is a binary tree which satisfies three
7+
* properties: left child is less than root node, right child is grater than root node, both left
8+
* and right childs must themselves be a BST.
9+
*
10+
* @author [Lakhan Nad](https://github.com/Lakhan-Nad)
11+
*/
12+
import java.util.Stack;
13+
14+
public class BSTIterative {
15+
/** Reference for the node of BST. */
16+
private Node root;
17+
18+
/** Default Constructor Initializes the root of BST with null. */
19+
BSTIterative() {
20+
root = null;
21+
}
22+
23+
/**
24+
* A method to insert a new value in BST. If the given value is already present in BST the
25+
* insertion is ignored.
26+
*
27+
* @param data the value to be inserted
28+
*/
29+
public void add(int data) {
30+
Node parent = null;
31+
Node temp = this.root;
32+
int rightOrLeft = -1;
33+
/* Finds the proper place this node can
34+
* be placed in according to rules of BST.
35+
*/
36+
while (temp != null) {
37+
if (temp.data > data) {
38+
parent = temp;
39+
temp = parent.left;
40+
rightOrLeft = 0;
41+
} else if (temp.data < data) {
42+
parent = temp;
43+
temp = parent.right;
44+
rightOrLeft = 1;
45+
} else {
46+
System.out.println(data + " is already present in BST.");
47+
return; // if data already present we ignore insertion
48+
}
49+
}
50+
/* Creates a newnode with the value passed
51+
* Since this data doesn't already exists
52+
*/
53+
Node newnode = new Node(data);
54+
/* If the parent node is null
55+
* then the insertion is to be done in
56+
* root itself.
57+
*/
58+
if (parent == null) {
59+
this.root = newnode;
60+
} else {
61+
/* Check if insertion is to be made in
62+
* left or right subtree.
63+
*/
64+
if (rightOrLeft == 0) {
65+
parent.left = newnode;
66+
} else {
67+
parent.right = newnode;
68+
}
69+
}
70+
}
71+
72+
/**
73+
* A method to delete the node in BST. If node is present it will be deleted
74+
*
75+
* @param data the value that needs to be deleted
76+
*/
77+
public void remove(int data) {
78+
Node parent = null;
79+
Node temp = this.root;
80+
int rightOrLeft = -1;
81+
/* Find the parent of the node and node itself
82+
* That is to be deleted.
83+
* parent variable store parent
84+
* temp stores node itself.
85+
* rightOrLeft use to keep track weather child
86+
* is left or right subtree
87+
*/
88+
while (temp != null) {
89+
if (temp.data == data) {
90+
break;
91+
} else if (temp.data > data) {
92+
parent = temp;
93+
temp = parent.left;
94+
rightOrLeft = 0;
95+
} else {
96+
parent = temp;
97+
temp = parent.right;
98+
rightOrLeft = 1;
99+
}
100+
}
101+
/* If temp is null than node with given value is not
102+
* present in our tree.
103+
*/
104+
if (temp != null) {
105+
Node replacement; // used to store the new values for replacing nodes
106+
if (temp.right == null && temp.left == null) { // Leaf node Case
107+
replacement = null;
108+
} else if (temp.right == null) { // Node with only right child
109+
replacement = temp.left;
110+
temp.left = null;
111+
} else if (temp.left == null) { // Node with only left child
112+
replacement = temp.right;
113+
temp.right = null;
114+
} else {
115+
/* If both left and right child are present
116+
* we replace this nodes data with
117+
* leftmost node's data in its right subtree
118+
* to maintain the balance of BST.
119+
* And then delete that node
120+
*/
121+
if (temp.right.left == null) {
122+
temp.data = temp.right.data;
123+
replacement = temp;
124+
temp.right = temp.right.right;
125+
} else {
126+
Node parent2 = temp.right;
127+
Node child = temp.right.left;
128+
while (child.left != null) {
129+
parent2 = child;
130+
child = parent2.left;
131+
}
132+
temp.data = child.data;
133+
parent2.left = child.right;
134+
replacement = temp;
135+
}
136+
}
137+
/* Change references of parent after
138+
* deleting the child.
139+
*/
140+
if (parent == null) {
141+
this.root = replacement;
142+
} else {
143+
if (rightOrLeft == 0) {
144+
parent.left = replacement;
145+
} else {
146+
parent.right = replacement;
147+
}
148+
}
149+
}
150+
}
151+
152+
/** A method for inorder traversal of BST. */
153+
public void inorder() {
154+
if (this.root == null) {
155+
System.out.println("This BST is empty.");
156+
return;
157+
}
158+
System.out.println("Inorder traversal of this tree is:");
159+
Stack<Node> st = new Stack<Node>();
160+
Node cur = this.root;
161+
while (cur != null || !st.empty()) {
162+
while (cur != null) {
163+
st.push(cur);
164+
cur = cur.left;
165+
}
166+
cur = st.pop();
167+
System.out.print(cur.data + " ");
168+
cur = cur.right;
169+
}
170+
System.out.println(); // for next line
171+
}
172+
173+
/** A method used to print postorder traversal of BST. */
174+
public void postorder() {
175+
if (this.root == null) {
176+
System.out.println("This BST is empty.");
177+
return;
178+
}
179+
System.out.println("Postorder traversal of this tree is:");
180+
Stack<Node> st = new Stack<Node>();
181+
Node cur = this.root, temp2;
182+
while (cur != null || !st.empty()) {
183+
if (cur != null) {
184+
st.push(cur);
185+
cur = cur.left;
186+
} else {
187+
temp2 = st.peek();
188+
if (temp2.right != null) {
189+
cur = temp2.right;
190+
} else {
191+
st.pop();
192+
while (!st.empty() && st.peek().right == temp2) {
193+
System.out.print(temp2.data + " ");
194+
temp2 = st.pop();
195+
}
196+
System.out.print(temp2.data + " ");
197+
}
198+
}
199+
}
200+
System.out.println(); // for next line
201+
}
202+
203+
/** Method used to display preorder traversal of BST. */
204+
public void preorder() {
205+
if (this.root == null) {
206+
System.out.println("This BST is empty.");
207+
return;
208+
}
209+
System.out.println("Preorder traversal of this tree is:");
210+
Stack<Node> st = new Stack<Node>();
211+
st.push(this.root);
212+
Node temp;
213+
while (!st.empty()) {
214+
temp = st.pop();
215+
System.out.print(temp.data + " ");
216+
if (temp.right != null) {
217+
st.push(temp.right);
218+
}
219+
if (temp.left != null) {
220+
st.push(temp.left);
221+
}
222+
}
223+
System.out.println(); // for next line
224+
}
225+
226+
/**
227+
* A method to check if given data exists in out Binary Search Tree.
228+
*
229+
* @param data the value that needs to be searched for
230+
* @return boolean representing if the value was find
231+
*/
232+
public boolean find(int data) {
233+
Node temp = this.root;
234+
/* Check if node exists
235+
*/
236+
while (temp != null) {
237+
if (temp.data > data) {
238+
temp = temp.left;
239+
} else if (temp.data < data) {
240+
temp = temp.right;
241+
} else {
242+
/* If found return true
243+
*/
244+
System.out.println(data + " is present in the BST.");
245+
return true;
246+
}
247+
}
248+
System.out.println(data + " not found.");
249+
return false;
250+
}
251+
252+
/** The Node class used for building binary search tree */
253+
private class Node {
254+
int data;
255+
Node left;
256+
Node right;
257+
258+
/** Constructor with data as parameter */
259+
Node(int d) {
260+
data = d;
261+
left = null;
262+
right = null;
263+
}
264+
}
265+
}

0 commit comments

Comments
 (0)