Data Structure and Algorithms are the most important concepts influencing every programming language. Binary Tree Implementation and Several Operations are no exception. Have you ever heard about the term ‘Binary Search Tree’ concept in Data Structure?
No worries if you haven’t encountered this topic before because you’re about to gain in-depth knowledge on it. If you ever find yourself struggling with BST or other Data Structure concepts, you can always get Data Structure Homework Help from our expert tutors at CodingZap.
So, fasten your seatbelts for an extensive discussion over the crucial concept of Binary Search Tree in Java. Let us start with a very basic discussion.
What Is Binary Search Tree In Java Programming Language?
You might already know about the “Tree concept” present in the Data Structures. The Tree concept is categorized under the Non-Linear Data Structure Concept. Because all the nodes or the elements don’t get stored in the memory in a sequential manner.
In the Tree Data Structure concept, there are many variations are present. The Binary Search Tree is one such variation. Here, the concept is developed around the two-node root which is popularly known as the Parent Node and Child Node or Leaf Node.
The Parent Node, Child Node, or Leaf Node can be divided further into three categories. These are the following:
Root Node: The Root Node is the main node of any Binary Search Tree. The main Root Node is the highest number of any root node present in the Binary Tree.
Left Child or Left Leaf Node: The node that is present at the left-hand side of any root node will be considered as the Left Child or Left Leaf Node. In the Binary Tree, the Left Child should always be smaller than the Main Root Node. It is the representative of Left Subtree.
Right Child or Right Leaf Node: The Right Child is the main representative of the Right Subtree that is present below the Right Child. In the case of the Binary Tree concept, the Right Child will always be greater in number than the main Root Node.
What Is Binary Search Tree Java Implementation Process?
Now, it is time to draft the Java program which will be used to implement the Binary Search Tree without causing any error. Here, the concept is based on creating a Node Container that will contain three types of information. One is Data, and another two are the addresses of two children.
One thing you should note is that the creation of a Binary Search Tree is not a simple job. Many advanced topics are used for creating such programs. So, be sure you have a nice grip on those concepts.
Program To Define The Process To Implement or Insert Elements Into The BST Using Java:
class BinaryST_Java {
class Node { // Class Node For Creating Node Structure
int key; // Taking Int Data From The Users
Node left, right;
public Node(int info){ // We will Not Create Private Node Root
key = info; // Inserting Int Data
left = right = null;
}
}
Node root; // Creating Root Node
BinaryST_Java(){ // Constructor For Binary Search Tree
root = null;
}
void insert(int key){ // Function To Insert A Node To BST
root = inRecur(root, key); // Creating New Node
}
Node inRecur(Node root, int key){ // Function To Recursively Insert Element
if (root == null){ // Condition To Check Empty Tree To Return Null
root = new Node(key); // Inserting Int Data To Node
return root; // We Will Return Root Here
}
if (key < root.key) // Inserting Element In The Left
root.left = inRecur(root.left, key); // Making Left Subtree
else if (key > root.key) // Inserting Element In The Right
root.right = inRecur(root.right, key);
return root; // We Will Return Root To Pointer
}
void print(){ // Function To Print The BST
Recurprint(root);
}
void Recurprint(Node root){ // Recuersive Print Function To Reduce Time Complexity
if (root != null) { // Checking Root Status
Recurprint(root.left); // Performing Inorder Traversal
System.out.print(root.key + "->");
Recurprint(root.right);
}
}
}
public class Main{
public static void main(String[] args) {
BinaryST_Java tree = new BinaryST_Java(); // Making Binary Search Tree Object
// Inserting Elements Into The Tree
tree.insert(10);
tree.insert(5);
tree.insert(3);
tree.insert(2);
tree.insert(15);
System.out.println("The Created Binary Search Tree: ");
tree.print(); // Printing The Entire BST
}
}
Steps Of The Program:
At first, a class node will be created that will hold all the values of ay node. In any one, there will be Int Data, And Left and Right variables with the Node form.
The creation of one constructor is necessary to point the nodes and to interconnect each and every node in the program.
The function to hold and insert the new node into the code will be declared. The function will first check whether the Binary Search Tree is empty or not. If it is empty it will create a new node first.
Now, after creating the node, it will check the data. If the data is less than the root element, then it will be placed at the left subtree.
Else, the data will be placed at the right subtree. And this process goes on in a recursive manner.
A function will again be created to print the BST in the necessary manner. That means the left subtree will be first printed. Then, the Main Root Node will be printed. And at last, the right subtree will be printed.
In the main function, some elements will be inserted with the help of the BST Object that has been created. Now, the print function will be used that is developed with the help of the Inorder traversal process.
Output:
From the above output, we can see that the element that is placed at the very left-most side will be printed first. So, the traversal of the left subtree can be done well with this program. As we are getting the entire node sequence, the program is marked as a working one.
What Is The Theory For Deleting Elements Into A Binary Search Tree?
Now, let us discuss the deletion operation on any designed BST. The Deletion or removal of any element is not as simple as inserting an element into the BST. The deletion operation also has some rules that need to be discussed carefully.
Here, we will make three kinds of scenarios that you might find while deleting any node from the BST. Let us look at those scenarios or cases one by one.
Case 1: Node With No Child
If you want to delete a node on which no children are present, that means, no other node is attached to the chosen node, then you should not be worried. You can delete the node from the BST and move with other operations.
Case 2: Node With Only One Child
In case, there is only one child is added to the node that is going to be deleted, you can do one simple operation. You can add the child to the above root of the deleted node. In this way, the concept will not be violated along the node will get deleted.
Case 3: Node With Two Children
Now, if you want to delete a node with two children, then the simple trick you need to use. Make the Node Left as the root node of the subtree. And the right node is kept as it is. That means the Node Left will become the root node to keep the rule of BST.
How To Do Binary Search Tree Java Delete Operation?
Now, it is time to make a draft code in Java programming language that will demonstrate the deleting process of any node from the Binary Search Tree. The code is a simple one where the elements first be searched & then deleted.
The code will be developed with the help of the BST Implementation Code. Deleting can only be possible if there is any element present. That is the reason, we have to first insert an element into the code and then delete some of them.
Program To Demonstrate The Delete Operation On Binary Search Trees:
class BST_Java {
class Node { // Class For Creating Node Structure
int key; // Taking Int Value From Main Function
Node left, right;
public Node(int info){ // Creating Public Node For Access
key = info;
left = right = null;
}
}
Node root; // Creating Root Node
BST_Java(){ // Constructor For Binary Search Tree
root = null; // We Will Return Node Here
}
void insert(int key){ // Function To Insert A Node To BST
root = inRecur(root, key);
}
Node inRecur(Node root, int key){ // Function To Recursively Insert Element
if (root == null){ // Condition To Check Empty Tree
root = new Node(key);
return root; // We Will Return Node Root
}
if (key < root.key) // Inserting Element In The Left
root.left = inRecur(root.left, key);
else if (key > root.key) // Inserting Element In The Right
root.right = inRecur(root.right, key);
return root; // Returning The Pointer
}
void del(int key) { // Function To Delete A Node
root = delr(root, key); // Accessing Public Node
}
Node delr(Node root, int key){ // Recusive Deleting Function
if (root == null) // If The Tree Is Empty
return root;
if (key < root.key)
root.left = delr(root.left, key); // Deleting From Left Tree
else if (key > root.key)
root.right = delr(root.right, key); // Deleting From Right Tree
else { // Condition For Nodes With One Child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
}
return root;
}
void print(){ // Function To Print The BST
Recurprint(root); // Performing Inorder Traversal
}
void Recurprint(Node root){ // Recuersive Print Function To Reduce Time Complexity
if (root != null) { // Checking Root Status
Recurprint(root.left);
System.out.print(root.key + "->");
Recurprint(root.right);
}
}
}
public class Main{
public static void main(String[] args) {
BST_Java tree = new BST_Java(); // Making Binary Search Tree Object
// Inserting Elements Into The Tree
tree.insert(10);
tree.insert(5);
tree.insert(3);
tree.insert(15);
System.out.print("The Created Binary Search Tree: ");
tree.print(); // Printing The Entire BST
System.out.println();
System.out.print("The New BST After Deletion: ");
tree.del(5); // Deleting The Element
tree.print(); // Printing The Entire Tree After Deletion
}
}
Steps Of The Program:
At first, we will follow the steps to create & insert elements into the BST those are discussed earlier.
Now for the delete operation, a function will be created. In this function, we will recursively check the presence of the element. If it is less than the Root, it will be on the Left Side. Otherwise, the node will be on the Right Subtree.
When we get the Node that should be deleted, it will be marked as Null so it will not be considered for printing purposes.
Now, in the main function, we will first print the entire BST. After the deletion operation, the printing operation will again be performed to see the changes.
Output:
From the above output, we can see that the BST designing was done completely well and the printing of the Binary Search Tree was completed without any error. Now, we have deleted an element from the tree and when we are again printing the tree, the element is now not present.
What Is The Theory For Searching Elements Into A Binary Search Tree?
Another important operation can be done with the Binary Search Tree. From the list of numbers that are present in the nodes, a particular number needs to be extracted.
And if the number is present in the list, it will be marked. To find out any element from the list, the following rules should be executed repeatedly. Here is the list of steps:
If the required number is less than the root number, go to the left subtree and find out.
If the required number is greater than the root number, go to the right subtree and find out.
We can go through the following image to clear the concept a bit more. In this case, a certain number needs to be found out with the help of the above-mentioned steps.
If you’re interested in discovering about Binary Seach Tree concept for other programming languages like C++, then you can have a look at our article on BST in C++.
How To Implement The Code For Searching An Element Into Binary Search Tree?
Now, we will declare the steps of code that are necessary to develop a system that will find out a certain number from a specific Binary Search Tree. Here, the above-declared rules will be followed to get back the presence data.
In this case, also, we need to first design the BST to find out any certain node number from the tree. So, the code for creating the Binary Search Tree will be used along with a new code snippet used for searching the node number.
Java Code To Find Out Any Specific Number From The Given Binary Search Tree:
class BST_Java {
class Node { // Class Node For Creating Node Structure
int key;
Node left, right;
public Node(int info){
key = info;
left = right = null;
}
}
Node root; // Creating Root Node
BST_Java(){ // Constructor For Binary Search Tree
root = null;
}
void insert(int key){ // Function To Insert A Node To BST
root = inRecur(root, key);
}
Node inRecur(Node root, int key){ // Function To Recursively Insert Element
if (root == null){ // Condition To Check Empty Tree
root = new Node(key);
return root;
}
if (key < root.key) // Inserting Element In The Left
root.left = inRecur(root.left, key);
else if (key > root.key) // Inserting Element In The Right
root.right = inRecur(root.right, key);
return root; // Returning The Pointer
}
String searchkey(int key){ // Search Function That Returns String Value
root = sear(root, key);
if (root!= null) // If Node Is Present
return "Yes";
else // If Node Is Not Present
return "No";
}
Node sear(Node root, int key){
if (root==null || root.key==key)
return root;
if (root.key > key)
return sear(root.left, key);
return sear(root.right, key);
}
void print(){ // Function To Print The BST
Recurprint(root);
}
void Recurprint(Node root){ // Recuersive Print Function To Reduce Time Complexity
if (root != null) { // Checking Root Status
Recurprint(root.left);
System.out.print(root.key + "->");
Recurprint(root.right);
}
}
}
public class Main{
public static void main(String[] args) {
BST_Java tree = new BST_Java(); // Making Binary Search Tree Object
// Inserting Elements Into The Tree
tree.insert(10);
tree.insert(5);
tree.insert(3);
tree.insert(15);
System.out.print("The Created Binary Search Tree: ");
tree.print(); // Printing The Entire BST
System.out.println();
String result = tree.searchkey(150); // Searching For The Key
System.out.println("Is The Key 150 Found In BST? : " + result); // Checking The Key
}
}
Steps Of The Program:
Follow the steps that are used to design a BST using the Java program by inserting elements.
Declare the function to check the presence of any element. The class will use the searching rule and find out the element and its root number.
If the element is giving the root number, then the element is present. So, the String Value “YES” will be shared. Otherwise, the String Value “NO” will get shared.
Output:
From the above screenshot, we can see that the elements of the BST are printing successfully. Now, we are checking the presence of any element in the BST. As the element is not present in the BST, it will provide the NO value to the output.
How Many Binary Search Trees With n Nodes Can Be Possible?
It is a very important and tricky question you can accept from your university faculty or even during your interview related to Data Structure. Here, the number of nodes will be given to you. And the question will be asked how many unique BSTs can be drawn with those number of nodes.
For that, you need to use the formula: Cn = (2n)! / ((n + 1)! * n!) Where n = 0, 1, 2, 3, …
If we consider the number of ‘n’ as 0, 1, 2, 3, … the values of the potential number of Unique BST can be 1, 1, 2, 5, 14, 42, 132, 429, … and so on. So, remember this trick to calculate or prompt provide an answer during your interview or viva.
Conclusion:
As we saw, the “Binary Tree Implementation and Several Operations” are really important to know.
Practice the code and the BST concept as much as possible to have a good grip on the Data Structures and Algorithm concepts. Try to define the Binary Search Tree code in other programming languages as well to excel in your skills.
It is always advisable to clear the basic programming concept before tackling such an important and challenging topic in Java. If your foundation in the theory of BST and Java is rock-hard, then such a topic will become a walk in the park for you.
