1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
| package com.chung;
import java.util.LinkedList;
import java.util.Queue;
import node.BinaryNode;
public class BinarySearchTreeByLinkedList {
BinaryNode root;
public BinaryNode getRoot() {
return root;
}
// Constructor
BinarySearchTreeByLinkedList() {
root = null;
}
// Insert values in BST
void insert(int value) {
root = insert(root, value);
}
// Helper Method
BinaryNode insert(BinaryNode currentNode, int value) {
if (currentNode == null) { // if root node is blank then insert new node there
System.out.println("Successfully inserted " + value + " in BST");
return createNewNode(value);
} else if (value <= currentNode.getValue()) {
currentNode.setLeft(insert(currentNode.getLeft(), value));
return currentNode;
} else {
currentNode.setRight(insert(currentNode.getRight(), value));
return currentNode;
}
}
// creates a new blank new node
public BinaryNode createNewNode(int value) {
BinaryNode node = new BinaryNode();
node.setValue(value);
return node;
}
// Deleting a node from BST
public void deleteNodeOfBST(int value) {
System.out.println("\n\nDeleting " + value + " from BST...");
deleteNodeOfBST(root,value);
}
// Helper Method for delete
public BinaryNode deleteNodeOfBST(BinaryNode root, int value) {
if (root == null) {
System.out.println("Value not found in BST");
return null;
}
if (value < root.getValue()) {
root.setLeft(deleteNodeOfBST(root.getLeft(), value));
} else if (value > root.getValue()) {
root.setRight(deleteNodeOfBST(root.getRight(), value));
} else { // If currentNode is the node to be deleted
if (root.getLeft() != null && root.getRight() != null) { // if nodeToBeDeleted have both children
BinaryNode temp = root;
BinaryNode minNodeForRight = minimumElement(temp.getRight());// Finding minimum element from right subtree
root.setValue(minNodeForRight.getValue()); // Replacing current node with minimum node from right subtree
root.setRight(deleteNodeOfBST(root.getRight(), minNodeForRight.getValue())); // Deleting minimum node from right now
} else if (root.getLeft() != null) {// if nodeToBeDeleted has only left child
root = root.getLeft();
} else if (root.getRight() != null) {// if nodeToBeDeleted has only right child
root = root.getRight();
} else // if nodeToBeDeleted do not have child (Leaf node)
root = null;
}
return root;
}// end of method
// Get minimum element in binary search tree
public static BinaryNode minimumElement(BinaryNode root) {
if (root.getLeft() == null)
return root;
else {
return minimumElement(root.getLeft());
}
}// end of method
// Search a node in BST
void searchForValue(int value) {
searchForValue(root, value);
}
// Search a node in BST
BinaryNode searchForValue(BinaryNode node, int value) {
if (node == null) {
System.out.println("Value: " + value + " not found in BST.");
return null;
} else if (node.getValue() == value) {
System.out.println("Value: " + value + " found in BST.");
return node;
} else if (value < node.getValue()) {
return searchForValue(node.getLeft(), value);
} else {
return searchForValue(node.getRight(), value);
}
}// end of method
// Level order traversal of BST
void levelOrderTraversal() {
Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
queue.add(root);
System.out.println("\nPrinting Level order traversal of Tree...");
if (root == null) {
System.out.println("Tree does not exists !");
return;
}
while (!queue.isEmpty()) {
BinaryNode presentNode = queue.remove();
System.out.print(presentNode.getValue() + " ");
if (presentNode.getLeft() != null)
queue.add(presentNode.getLeft());
if (presentNode.getRight() != null)
queue.add(presentNode.getRight());
}
}// end of method
// Delete entire BST
public void deleteTree() {
System.out.println("Deleting entire Tree...");
root = null;
System.out.println("Tree deleted successfully !");
}// end of method
void printTreeGraphically(){
Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
Queue<Integer> level = new LinkedList<Integer>();
int CurrentLevel = 1;
boolean previousLevelWasAllNull = false;
queue.add(root);
level.add(1);
if(root == null){
System.out.println("Tree does not exists");
return;
}
while(!queue.isEmpty()){
if(CurrentLevel == level.peek()){
if(queue.peek() == null){
queue.add(null);
level.add(CurrentLevel +1);
} else {
queue.add(queue.peek().getLeft());
level.add(CurrentLevel + 1);
queue.add(queue.peek().getRight());
level.add(CurrentLevel + 1);
previousLevelWasAllNull = false;
}
System.out.print(queue.remove() + " ");
level.remove();
} else {
System.out.println("\n");
CurrentLevel++;
if(previousLevelWasAllNull == true){
break;
}
previousLevelWasAllNull = true;
}
}
}
}// end of class
|