Let’s Build a Binary Search Tree in Java!
Let’s Build a Binary Search Tree in Java!
I know you know that a BST (Binary Search Tree) uses dynamic memory, meaning it employs discontinuous memory allocation similar to a linked list, unlike an array which uses continuous memory allocation.
Before getting your hands dirty, I will shed some light on some rapid fire facts. 🔥🔥🔥 Fact 1: BSTs use dynamic memory allocation for their nodes. Each node in the tree is dynamically allocated in memory and contains data and pointers to its left and right child nodes (subtrees). This dynamic allocation allows the BST to grow and shrink as elements are inserted or removed.
Fact2: BST offer efficient search, insert, and delete operations when the tree is balanced. The time complexity for these operations in a balanced BST is O(log n), where “n” is the number of nodes in the tree.
Fact3: (Only for people who read yesterday’s blog about BST) 🤩 it’s essential to note that the efficiency of BST operations depends on the **balance **of the tree. In the worst-case scenario, when the tree is heavily **unbalanced **(resembling a linked list), the time complexity for these operations can degrade to O(n), where “n” is the number of nodes in the tree. This can happen, for example, if elements are inserted in a **sorted ****order into the BST. **Don’t worry we have techniques such as **AVL trees **and **Red-Black trees **to keep the tree balanced automatically. I will explore those techniques in the coming blogs.👍
NO MORE TALKING, lets dive into coding 🚀
I am using IntelliJ IDEA Community Edition as the IDE. Create a Java project and you will get as follows:
Now lets create some BLUE PRINTS!
Create a class **TreeNode **in src/main/java/org/example
class TreeNode {
int key;
TreeNode left;
TreeNode right;
public TreeNode(int key) {
this.key = key;
this.left = null;
this.right = null;
}
}
Create another class **BinarySearchTree **in src/main/java/org/example
First, let’s write the skeleton of the class. No need to reinvent the wheel here; we already know what behaviours a BST class should exhibit.
Remember: Like all of us, this class also has some public behaviours and private behaviours! 😆 Let’s look at what the public behaviours first.
-
insert
-
search
-
delete
-
inOrderTraversal
-
preOrderTraversal
-
postOrderTraversal
package org.example;
import java.util.Optional;
public class BinarySearchTree {
private TreeNode root;
public BinarySearchTree(){
this.root = null;
}
public void insert(){
// Behaviour - 1
}
public Optional<TreeNode> search(int key){
// Behaviour - 2
return null;
}
public void delete(int key){
// Behaviour - 3
}
public void inorderTraversal(){
// Behaviour - 5
}
public void preorderTraversal(){
// Behaviour - 6
}
public void postorderTraversal(){
// Behaviour - 7
}
}
lets implement insert
public void insert(int key){
root = insertRecursive(root, key);
}
private TreeNode insertRecursive(TreeNode node, int key) {
if (node == null) {
return new TreeNode(key);
}
if (key < node.key) {
node.left = insertRecursive(node.left, key);
} else if (key > node.key) {
node.right = insertRecursive(node.right, key);
}
return node;
}
lets implement search
public Optional<TreeNode> search(int key) {
return searchRecursive(root, key);
}
private Optional<TreeNode> searchRecursive(TreeNode node, int key) {
if (node == null || node.key == key) {
return Optional.ofNullable(node);
}
if (key < node.key) {
return searchRecursive(node.left, key);
} else {
return searchRecursive(node.right, key);
}
}
Note: Optional.ofNullable() is a method provided by the java.util.Optional class in Java. It is used to create an Optional instance that may or may not contain a non-null value.
lets implement delete
public void delete(int key) {
root = deleteRecursive(root, key);
}
private TreeNode deleteRecursive(TreeNode node, int key) {
if (node == null) {
return node;
}
if (key < node.key) {
node.left = deleteRecursive(node.left, key);
} else if (key > node.key) {
node.right = deleteRecursive(node.right, key);
} else {
// Node to be deleted is found
// Case 1: Node has no children
if (node.left == null && node.right == null) {
node = null;
}
// Case 2: Node has one child (right child)
else if (node.left == null) {
node = node.right;
}
// Case 3: Node has one child (left child)
else if (node.right == null) {
node = node.left;
}
// Case 4: Node has two children
else {
TreeNode successor = findMinNode(node.right);
node.key = successor.key;
node.right = deleteRecursive(node.right, successor.key);
}
}
return node;
}
private TreeNode findMinNode(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
I know what you are thinking, you want to know more about **Case 4: Node has two children **right?
Suppose we have the following binary search tree:
50
/ \
30 70
/ \ / \
20 40 60 80
Now, let’s say we want to delete the node with key 50 (the root), which has two children. To do this:
-
We find the successor node, which is the smallest node in its right subtree. In this case, the successor is 60 (the leftmost node in the right subtree of the root).
-
We copy the key value of the successor (60) to the node being deleted (50). The tree now looks like:
60
/ \
30 70
/ \ / \
20 40 - 80
- Since the successor (60) had at most one child (in this case, it has no children), we can simply delete the successor node.
I heard you! don’t worry i will explain the control flow.
node will be represented as [left,key,right]
====================================
BLOCK-1-INPUT : Key = 50
*50
/ \
*30 *70
/ \ / \
20 40 60 80
public void delete(int key) {
root = deleteRecursive(root, key);
- root = **deleteRecursive( [ 30, 50, 70 ], 50 ) **====> CALL 1 (waiting to get the result)
====================================
BLOCK-2-INPUT : node = [30,50,70] key = 50
// Case 4: Node has two children
else {
TreeNode successor = findMinNode(node.right);
node.key = successor.key;
node.right = deleteRecursive(node.right, successor.key);
}
}
return node;
}
-
enter Case 4: Node has two children
-
successor = [null,60,null]
-
node.key = successor.key;
-
node = [30,60,70]
-
node.right = deleteRecursive( [60,70,80] , 60 ) ====> CALL 2*(waiting to get the result)*
50
/ \
30 *70
/ \ / \
20 40 *60 *80
====================================
BLOCK-3-INPUT : node = [60,70,80] key = 60
if (key < node.key) {
node.left = deleteRecursive(node.left, key);
- 60 < 70 = true
50
/ \
30 70
/ \ / \
20 40 *60 80
/ \
null null
- node.left = **deleteRecursive([null,60,null], 60) **====> **CALL3 **(waiting to get the result)
====================================
BLOCK-4-INPUT : node[null,60,null], Key = 60
// Case 1: Node has no children
if (node.left == null && node.right == null) {
node = null;
}
-
enter Case 1: Node has no children
-
node = null;
-
return null;
====================================
Go Back to BLOCK-3 (node = [60, 70, 80])
if (key < node.key) {
node.left = deleteRecursive(node.left, key);
-
node.left = null;
-
return [null,70,80];
====================================
Go Back to BLOCK-2 (node = [30, 60, 70])
// Case 4: Node has two children
else {
TreeNode successor = findMinNode(node.right);
node.key = successor.key;
node.right = deleteRecursive(node.right, successor.key);
}
}
return node;
}
-
node.right = [ null, 70, 80 ]
-
return [ 30, 60, [null,70,80] ]
====================================
Go Back to BLOCK-1 (node = [30, 50, 70])
- root = node[ 30, 60, [null,70,80] ]
60
/ \
30 70
/ \ \
20 40 80
As we can see, the tree still maintains the binary search tree property, and the node with key 50 has been successfully deleted.
lets implement inOrderTraversal
public void inorderTraversal() {
inorderTraversalRecursive(root);
System.out.println();
}
private void inorderTraversalRecursive(TreeNode node) {
if (node != null) {
inorderTraversalRecursive(node.left);
System.out.print(node.key + " ");
inorderTraversalRecursive(node.right);
}
}
In the in-order traversal, we visit the left subtree, then the current node, and finally the right subtree, following the order (left, node, right). This process is performed recursively for each subtree until all nodes have been visited.
50
/ \
30 70
/ \ / \
20 40 60 80
The in-order traversal will visit the nodes in the following order: 20, 30, 40, 50, 60, 70, 80.
lets implement preOrderTraversal
public void preorderTraversal() {
preorderTraversalRecursive(root);
System.out.println();
}
private void preorderTraversalRecursive(TreeNode node) {
if (node != null) {
System.out.print(node.key + " ");
preorderTraversalRecursive(node.left);
preorderTraversalRecursive(node.right);
}
}
Pre-order traversal is another method used to traverse a binary tree, where we visit the nodes in the order (node, left, right). In pre-order traversal, we start by visiting the current node, then the left subtree, and finally the right subtree. This process is performed recursively for each subtree until all nodes have been visited.
50
/ \
30 70
/ \ / \
20 40 60 80
The pre-order traversal will visit the nodes in the following order: 50, 30, 20, 40, 70, 60, 80.
lets implement postOrderTraversal
public void postorderTraversal() {
postorderTraversalRecursive(root);
System.out.println();
}
private void postorderTraversalRecursive(TreeNode node) {
if (node != null) {
postorderTraversalRecursive(node.left);
postorderTraversalRecursive(node.right);
System.out.print(node.key + " ");
}
}
Post-order traversal is yet another method used to traverse a binary tree, where we visit the nodes in the order (left, right, node). In post-order traversal, we start by visiting the left subtree, then the right subtree, and finally the current node. This process is performed recursively for each subtree until all nodes have been visited.
50
/ \
30 70
/ \ / \
20 40 60 80
The post-order traversal will visit the nodes in the following order: 20, 40, 30, 60, 80, 70, 50.
Congratulations 🎉 , now you know how to create a Binary Search Tree in Java.
One Moment : Thank you for taking the time to read my blog. I hope you found it helpful, insightful, or even entertaining. If it made a positive impact on your day or provided you with valuable information, I’d be thrilled to know!
If you enjoyed the content and would like to show your appreciation, you can support me in two ways:
-
Give it a Clap: Just click on the 👏 button at the end of the article. Each clap is a virtual pat on the back and a way to let me know that you liked the blog.
-
Buy Me a Coffee: If you’re feeling extra generous and would like to support my work further. To leave a tip, simply click on the “Tip” button, and any amount you’re comfortable with is greatly appreciated. Your contribution will keep me fueled and motivated to create more content in the future.
Your support means a lot to me, and it encourages me to continue sharing my knowledge and experiences. I’m grateful for each and every reader who finds value in what I write. 🙏
❤️ Feeling the love? Give me a tip on Medium!