Skip to content

Commit f57e4c6

Browse files
batCoder95batCoder95
authored
Merge pull request #3 from VatsalGosaliya/BSTBranch
Bst branch
2 parents a37df43 + 357b466 commit f57e4c6

3 files changed

Lines changed: 185 additions & 0 deletions

File tree

‎binary-search-tree/BinarySearchTree.java‎

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
import java.util.Stack;
2+
3+
class BinarySearchTree {
4+
private static TreeNode root = null;
5+
6+
BinarySearchTree(int data) {
7+
TreeNode node = new TreeNode(data);
8+
root = node;
9+
}
10+
11+
public void traverseInorder(){
12+
System.out.print("START -> ");
13+
Stack<TreeNode> stack = new Stack<TreeNode>();
14+
TreeNode ptr = root;
15+
boolean done = false;
16+
17+
while(!done){
18+
if(ptr != null ){
19+
stack.push(ptr);
20+
ptr = ptr.getLeft();
21+
}
22+
else{
23+
if(!stack.isEmpty()){
24+
ptr = stack.pop();
25+
System.out.print(ptr.getData()+" -> ");
26+
ptr = ptr.getRight();
27+
}
28+
else
29+
done = true;
30+
}
31+
}
32+
System.out.println("END");
33+
}
34+
35+
public void traversePreorder(){
36+
System.out.print("START -> ");
37+
Stack<TreeNode> stack = new Stack<TreeNode>();
38+
stack.push(root);
39+
40+
while(!stack.isEmpty()){
41+
TreeNode node = stack.pop();
42+
System.out.print(node.getData()+" -> ");
43+
if(node.getRight() != null)
44+
stack.push(node.getRight());
45+
if(node.getLeft() != null)
46+
stack.push(node.getLeft());
47+
}
48+
System.out.println("END");
49+
}
50+
51+
public void traversePostorder(){
52+
System.out.print("START -> ");
53+
TreeNode node;
54+
Stack<TreeNode> stack1 = new Stack<TreeNode>();
55+
Stack<TreeNode> stack2 = new Stack<TreeNode>();
56+
stack1.push(root);
57+
while(!stack1.isEmpty()){
58+
node = stack1.pop();
59+
stack2.push(node);
60+
if(node.getLeft() != null)
61+
stack1.push(node.getLeft());
62+
if(node.getRight() != null)
63+
stack1.push(node.getRight());
64+
}
65+
while(!stack2.isEmpty()){
66+
node = stack2.pop();
67+
System.out.print(node.getData()+" -> ");
68+
}
69+
System.out.println("END");
70+
}
71+
72+
public void insertNode(int data){
73+
TreeNode node = new TreeNode(data);
74+
TreeNode ptr = root;
75+
boolean done = false;
76+
77+
while (!done) {
78+
if(node.getData() <= ptr.getData()){
79+
if(ptr.getLeft() != null)
80+
ptr = ptr.getLeft();
81+
else{
82+
ptr.setLeft(node);
83+
done = true;
84+
}
85+
}
86+
else{
87+
if(ptr.getRight() != null)
88+
ptr = ptr.getRight();
89+
else{
90+
ptr.setRight(node);
91+
done = true;
92+
}
93+
}
94+
}
95+
}
96+
97+
public void deleteNode(int data){
98+
if(root == null)
99+
System.out.print("Tree Empty !");
100+
else
101+
root = delete(root, data);
102+
}
103+
104+
public TreeNode delete(TreeNode root, int data){
105+
TreeNode p,p2,n;
106+
107+
if (root.getData() == data)
108+
{
109+
TreeNode lt, rt;
110+
lt = root.getLeft();
111+
rt = root.getRight();
112+
if (lt == null && rt == null)
113+
return null;
114+
else if (lt == null)
115+
{
116+
p = rt;
117+
return p;
118+
}
119+
else if (rt == null)
120+
{
121+
p = lt;
122+
return p;
123+
}
124+
else
125+
{
126+
p2 = rt;
127+
p = rt;
128+
while (p.getLeft() != null)
129+
p = p.getLeft();
130+
p.setLeft(lt);
131+
return p2;
132+
}
133+
}
134+
if (data < root.getData())
135+
{
136+
n = delete(root.getLeft(), data);
137+
root.setLeft(n);
138+
}
139+
else
140+
{
141+
n = delete(root.getRight(), data);
142+
root.setRight(n);
143+
}
144+
return root;
145+
}
146+
147+
148+
public static void main(String[] args) {
149+
// TODO Auto-generated method stub
150+
BinarySearchTree T = new BinarySearchTree(20);
151+
T.insertNode(15);
152+
T.insertNode(25);
153+
T.insertNode(13);
154+
T.insertNode(17);
155+
T.insertNode(22);
156+
T.insertNode(28);
157+
T.traverseInorder();
158+
T.deleteNode(20);
159+
T.traversePreorder();
160+
T.traversePostorder();
161+
}
162+
163+
}

‎binary-search-tree/TreeNode.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class TreeNode{
2+
private int data;
3+
private TreeNode left = null;
4+
private TreeNode right = null;
5+
6+
TreeNode(int data){
7+
this.data = data;
8+
}
9+
10+
public int getData(){ return this.data; }
11+
public TreeNode getLeft(){ return this.left; }
12+
public TreeNode getRight(){ return this.right; }
13+
14+
public void setData(int data){ this.data = data; }
15+
public void setLeft(TreeNode left){ this.left = left; }
16+
public void setRight(TreeNode right){ this.right = right; }
17+
}

‎binary-search-tree/info‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
Java files for binary search tree
2+
3+
I have hardcoded the insertion and deletion operations, instead of giving the user choice feature.
4+
The main aim of this repository is the core algorithm, not user interaction.
5+
If needed, switch case or other similar structures can be used to let the user decide what methods to call at what time.

0 commit comments

Comments
 (0)