Table of Contents
Binary search trees (BSTs) are a fundamental data structure used to store data in a way that allows quick searches, inserts, and deletes. In this comprehensive guide, we will cover everything you need to know about implementing binary search trees in Java.
What is a Binary Search Tree?
A binary search tree is a binary tree that satisfies the binary search tree property – all left descendants ≤ node < all right descendants. This ordering allows binary search for fast lookup, addition and removal of elements.
The node at the top of the tree is called the root. Each node can have left and right subtrees. Nodes with no children are called leaf nodes.
Here is what a sample binary search tree looks like:
15
/ \
5 20
/ \ / \
2 8 17 25
\
10 In this tree:
- 15 is the root node
- 5, 20 are child nodes
- 2, 8, 17, 25 are leaf nodes
- 10 has one child node (8)
The binary search tree ordering can be seen here:
- Left subtree nodes (2, 5, 8, 10) ≤ root node (15)
- Right subtree nodes (17, 20, 25) ≥ root node (15)
This ordering allows fast lookup – we can discard half the tree at each comparison. Searching for 14 allows us to ignore the right subtree entirely.
The operations allowed on a binary search tree are:
- Search – Check if a value is present
- Insert – Add a new element
- Delete – Remove an existing element
Additionally, we need to be able to traverse a binary search tree to display all elements it contains.
Now that we understand the basics of a BST, let‘s look at how to implement one in Java.
Implementing a Binary Search Tree in Java
We will implement two classes to represent our binary search tree:
- BSTNode – Represents each node in the tree
- BST – Binary search tree class
BSTNode
class BSTNode {
int data;
BSTNode left;
BSTNode right;
BSTNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
} The BSTNode class represents each node in the binary search tree.
It contains:
- data – integer data the node contains
- left – reference to the left child node
- right – reference to the right child node
The constructor allows creating a new node and initializing the left and right child nodes to null.
BST Class
class BST {
private BSTNode root;
// methods will go here
}The BST class represents the full binary search tree. It holds a reference to the root node of the tree.
We will implement BST methods to allow adding, removing and finding nodes in the tree.
Before we can do that, we need ways to traverse the binary tree.
Binary Tree Traversal
Since a binary tree is not a linear data structure like a linked list or array, we need special techniques to traverse it and visit each node. There are two common ways to traverse a binary tree:
- Depth First Traversal
- Breadth First Traversal
We will look at both these traversals and how to implement them in Java.
1. Depth First Traversal
In depth first traversal, we start at the root node and explore each branch completely before moving on to the next branch.
There are 3 types of depth first traversals:
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
The difference is the order in which we visit nodes, relative to traversing their left and right subtrees.
Preorder Traversal
In preorder traversal, we visit each node before (pre) its left and right children.
Algorithm:
preorder(node)
visit(node)
preorder(node.left)
preorder(node.right)For the sample tree above, this gives the order as:
15, 5, 2, 8, 10, 20, 17, 25
Here is how to implement preorder traversal in Java:
void preorder(BSTNode node) {
if(node == null)
return;
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}The method is recursive. For each node, we first print its data, then traverse the left and right subtrees using recursion.
Inorder Traversal
In inorder traversal, we visit each node after (in) traversing its left subtree but before (in) traversing its right subtree.
Algorithm:
inorder(node)
inorder(node.left)
visit(node)
inorder(node.right) For our sample tree, this gives:
2, 5, 8, 10, 15, 17, 20, 25
Nodes are visited in ascending order. Here is how it is implemented:
void inorder(BSTNode node) {
if(node == null)
return;
inorder(node.left);
System.out.print(node.data +" ");
inorder(node.right);
}Again this uses recursion to traverse left subtree first, then prints node‘s data and finally right subtree.
Postorder Traversal
In postorder traversal, we visit each node after (post) traversing its left and right subtrees.
Algorithm:
postorder(node)
postorder(node.left)
postorder(node.right)
visit(node)Node visiting order for sample tree:
2, 10, 8, 5, 17, 25, 20, 15
And here is the implementation:
void postorder(BSTNode node) {
if(node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.print(node.data +" ");
} 2. Breadth First Traversal
In breadth first traversal, we traverse the tree level by level. All nodes at depth n are visited before those at depth n+1. This is also called level order traversal.
We use a queue to facilitate the traversal –
- Enqueue root node
- Dequeue a node N and
- Print N
- Enqueue N‘s left and right children
- Repeat Step 2 until queue is empty
void levelorder(BSTNode node) {
Queue q = new LinkedList();
q.add(node);
while(!q.isEmpty()) {
BSTNode n = q.remove();
System.out.print(n.data + " ");
if(n.left != null)
q.add(n.left);
if(n.right != null)
q.add(n.right);
}
} Level order traversal visits nodes in this order – 15, 5, 20, 2, 8, 17, 25, 10
Now that we know how to traverse a binary tree, we can move on to core BST operations!
BST Operations in Java
The main operations we want to support on our binary search tree are:
- Insert – add a new node
- Search – find a value in the tree
- Delete – remove a node
Let‘s look at the algorithm and implementation for each.
Our BST class contains the root node, along with insert, search and delete methods.
class BST {
private BSTNode root;
// BST methods
public void insert(int data) { }
public boolean search(int data) { }
public void delete(int data) { }
}1. Insert Operation
To insert a new node with value data into a BST:
Algorithm:
- If tree is empty, new node becomes root
- Otherwise
- Set current as root
- Traverse the tree till you reach a leaf node L, such that, value of L is > data
- Add new node as a child of leaf L
For example, inserting 14 into the below BST:
15 15
/ \ Insert 14 / \
5 20 =========> 5 20
\ / \
14 17 25
And here is the Java implementation of insert:
// inserts a node with given data into BST
public void insert(int data) {
BSTNode newNode = new BSTNode(data);
if(root == null) {
root = newNode;
return;
}
BSTNode current = root;
BSTNode parent = null;
while(true) {
parent = current;
// traverse left subtree if data is less than current
if(data < current.data) {
current = current.left;
if(current == null) {
parent.left = newNode;
return;
}
// traverse right subtree
} else {
current = current.right;
if(current == null) {
parent.right = newNode;
return;
}
}
}
} Walkthrough:
- Create a new node with given data
- If tree empty, new node becomes root
- Otherwise, traverse tree till we reach left/right null child
- Add new node as that child
The average time complexity is O(log n) as we eliminate 1 subtree at every step.
2. Search Operation
To check if a value data exists in the BST or not:
Algorithm:
- Set current as root
- Traverse tree nodes recursively
- If node data == data, return true
- Else if data < current.data, traverse left subtree
- Else traverse right subtree
- Node not found, return false
Implementation:
public boolean search(int data) {
return searchHelper(root, data);
}
private boolean searchHelper(BSTNode root, int data) {
if(root == null) {
return false;
}
if(root.data == data) {
return true;
}
if(data < root.data)
return searchHelper(root.left, data);
else
return searchHelper(root.right, data);
} Search complexity is O(log n). At every step, we remove one subtree from consideration making the algorithm very fast.
3. Delete Operation
Deleting nodes from a binary search tree is tricky because:
- Node to be deleted can be a leaf or have one/two children
- We have to maintain the binary search tree properties after deletion
There are 3 cases for node deletion:
1. Node is a Leaf Node
Deleting a leaf node is easy. Simply remove the reference to that node from its parent node.
2. Node has One Child
Copy the child node reference to the node‘s parent and delete it.
3. Node Has Two Children
- Find node‘s inorder successor from right subtree
- Copy contents of successor to node
- Recursively delete the successor
An inorder successor is the smallest element in node‘s right subtree.
After deletion, successor‘s right subtree gets attached to node.
Here is the implementation of node deletion:
public void delete(int data) {
root = deleteHelper(root, data);
}
private BSTNode deleteHelper(BSTNode root, int data) {
if (root == null)
return root;
if (data < root.data)
root.left = deleteHelper(root.left, data);
else if (data > root.data)
root.right = deleteHelper(root.right, data);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = findMin(root.right);
root.right = deleteHelper(root.right, root.data);
}
return root;
}Breaking it down:
- If empty tree, return
- Recursively find node, traversing left/right based on value
- When node found
- Case 1, 2 : Directly modify child references
- Case 3: Replace with inorder successor, recursively delete successor
findMin() method finds the minimum value node in right subtree. Its reference gets copied to current node, retaining BST structure.
The overall time complexity is O(log n).
Now that we have done the 3 main operations let‘s do some example queries!
Binary Search Tree Usage
Let‘s take our BST class for a spin with some sample inserts, searches and deletes.
public class Main {
public static void main(String[] args) {
BST bst = new BST();
// insert few nodes
bst.insert(15);
bst.insert(10);
bst.insert(20);
bst.insert(25);
// search some nodes
System.out.println(bst.search(10)); // true
System.out.println(bst.search(5)); // false
// traverse tree
bst.inorder(); // 10 15 20 25
// delete leaf node
bst.delete(25);
bst.inorder(); // 10 15 20
// delete node with 1 child
bst.delete(20);
bst.inorder(); // 10 15
// delete root node
bst.delete(15);
bst.inorder(); // 10
}
}The output shows:
- Inserting nodes
- Search working correctly
- Inorder traversal displaying inserted nodes
- Deleting leaf, node with single child and root node
Thus, our BST implementation along with traversal methods allows efficiently organizing, searching and mutating tree data.
Conclusion
We have gone over everything needed to fully understand and implement binary search trees in Java.
Key points:
- Binary search trees allow fast lookup, insert and delete by maintaining node ordering (left < node < right)
- Different types of tree traversals (preorder, inorder etc) visit nodes in specific sequence
- Insert and delete require some care to preserve BST ordering but can be done efficiently
- Average time for search, insert, delete is O(log n) due to tree halves being discarded ea step
BSTs have many applications from databases (MySQL) to router algorithms due to their speed and flexibility.
You now have the knowledge to leverage binary search trees to organize data for ultrafast access in your Java programs!