Trees are one of the most significant data structures in Java. There are various types of trees offered in Java but we will be specifically focusing on Binary search trees.
Table of Contents
In this article, we will be discussing the working of a binary search tree in Java. Along with that, we will also explore some crucial operations performed on a binary search tree.
If you have studied trees before, these terminologies must have come across you. These terms are very important to understand first before diving into the concepts and functionalities of a binary search tree in Java.
Node: It is a unit that the tree is made up of. Each node contains a piece of data and a pointer to other nodes in the tree.
Children: A successor node in the tree. Except for leaves (last nodes), every node in a binary tree can have a maximum of two children.
Parent: A predecessor node in the tree. Every node has a parent, except the root node.
Root: A root is the starting node in a tree. It does not have a parent as it is the first node in the tree.
Leaves: These are the last nodes in a tree, making them the end terminals of the tree. Hence, leaves do not have any children.
A binary tree is a specific type of tree where each node, excluding the leaves, has two children. A binary search tree extends this concept of a binary tree by fulfilling the following conditions,
This is made sure at the time of insertion of data in the nodes. These properties might seem trivial but they proved to be very helpful in solving various algorithmic problems. On top of that, a Binary search tree in Java also supports all the tasks done using a simple binary tree while taking significantly lesser time.
For implementing a Binary Search Tree in Java, first of all, you need to create a Node class that stores the data to be saved in the nodes along with right and left variables of Node type to keep a reference of each child.
See Code:
Static class Node { Public int data; Public Node left; Public Node right; Public Node(int data) { this.data = data; this.right = null; this.left = null; } }
After that you can start adding nodes to your binary search tree, The first Node is usually called the root to make the code easier to understand:
public class BinarySearchTree { Node root; public BinarySearchTree() { this.root = null; }
The Insertion process requires a method that creates a new node and inserts it in the tree at the right position depending on the data to be inserted.
As per the rule, if the value to be inserted is less than the parent node, a left child node is created whereas if the value is greater than a right child will be created. Lastly, the value will be added to the newly created node.
This scenario is for when we just have a root in a tree but if we already have some level in a binary search tree. The following steps are performed to traverse through the tree till the last node (leave) where the new node will be inserted.
The following code demonstrates the above-explained process in Java:
public Node root; public BinarySearchTree() { this.root = null; } // insert method public void insertData(int newData) { this.root = insert(root, newData); } public Node insertData (Node root, int newData) { // Case 1: when root is null if (root == null) { // Insert new data, if root is null. root = new Node(newData) return root; } // Checking whether the root data is same or equal to newData else if (root.data >= newData) { // if root data is greater than the new data then go to the left sub-tree root.left = insert(root.left, newData); } else { // if current root data is less than the new data then go to the right sub-tree root.right = insert(root.right, newData); } return root; } //Traversing the tree public void preorder() { preorder(root); } public void preorder(Node root) { if (root == null) { return; } System.out.print(root.data + ", "); preorder(root.left); preorder(root.right); } public static void main(String[] args) { BinarySearchTree obj1 = new BinarySearchTree(); // calling the the method insert obj1.insertData(2); obj1.insertData(8); obj1.insertData(1); obj1.insertData(4); obj1.insertData(6); obj1.preorder(); } }
Output Will be: 2 1 8 4 6
Deletion is a relatively complicated task than insertion, this is because deletion depends on the node that needs to be deleted. If the node to be deleted has no children (means, it is a leaf) then it can be easily removed from the tree. If a node has one child, after deleting that node the child has to be moved up to replace the deleted node.
It gets trickier when we have to delete a node with two children. First, we need to find the node with the smallest value in the right subtree. That will now replace the deleted node.
The following code is demonstrating all three scenarios for deleting a node when the node to be deleted has no child, 1 child or 2 children:
public void nodeDeletion(Node node) { nodeDeletion(this.root, node); } private Node nodeDeletion (Node root, Node node) { if (root == null) { return null; } else if (node.data < root.data) { // goes to left sub tree root.left = nodeDeletion(root.left, node); } else if (node.data > root.data) { // goes to right sub tree root.right = nodeDeletion(root.right, node); } else if(root.data==node.data){ // case 3: 2 children if (root.left != null && root.right != null) { int lmax = findMaxData(root.left); root.data = lmax; root.left = nodeDeletion(root.left, new Node(lmax)); return root; } //case 2: one child else if (root.left != null) { return root.left; } else if (root.right != null) { return root.right; } //case 1: no child else { return null; } } return root; } public static void main(String[] args) // Implementing on the previously made object (obj1) obj1.nodeDeletion (new Node(6)); obj.preorder(); } }
Output : 2 1 8 4
The process of searching in a binary search tree is quite straightforward. To search for a value, three conditions are needed to be checked,
These three steps will be repeated until the value is found. If the value is not found and you have reached the leaves, it will indicate that the value does not exist in the tree.
public boolean searchData(int data) { return search(this.root, data); } private boolean searchData(Node root, int data) { if (root == null) { return false; } else if (root.data == data) { return true; } else if (root.data > data) { return search(root.left, data); } return searchData(root.right, data); } //Traversing the tree public void preorder() { preorder(root); System.out.println(); } public void preorder(Node root) { if (root == null) { return; } System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } public static void main(String[] args) { // Applying on the previously made object, obj1 obj1.preorder(); System.out.println(obj1.search(1)); System.out.println(obj1.search(7)); } }
Output : 2 1 8 4 true false
A binary search tree in Java is an extremely useful data structure. This article explores various operations on a binary search tree along with their Java codes in java.
Also Read: A Guide to the Java ExecutorService
It should be adequate to bring you to pace with the basics of the binary search tree in Java and its practical uses.
Shaharyar Lalani is a developer with a strong interest in business analysis, project management, and UX design. He writes and teaches extensively on themes current in the world of web and app development, especially in Java technology.
Create a free profile and find your next great opportunity.
Sign up and find a perfect match for your team.
Xperti vets skilled professionals with its unique talent-matching process.
Connect and engage with technology enthusiasts.
© Xperti.io All Rights Reserved
Privacy
Terms of use