Binary Search Tree Program in Java
Binary Search Tree Program
Binary Search Tree Program in Java helps you understand how to implement one of the most important tree data structures used in searching and sorting problems.
A Binary Search Tree (BST) is a special type of binary tree where:
- Left subtree contains values less than root
- Right subtree contains values greater than root
- This property makes searching, insertion, and deletion efficient.
Binary Search Tree Program in Java
What is a Binary Search Tree?
A Binary Search Tree (BST) is a binary tree with an ordering property:
Left < Root < Right
Example BST:
50
/ \
30 70
/ \ / \
20 40 60 80
Representation of Binary Search Tree:
- The representation of a BST is similar to that of a binary tree. The order of a BST is ‘2’. Each node can have at most two children.
- Only difference between the two is that there is a certain criteria of arrangement or insertion of the elements based on their comparisons with the root node and the sub tree segment they are added to.
Operations in a Binary Search Tree:
- Traversal
- Searching
- Insertion
- Deletion
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Algorithms for Binary Search Tree
Insertion
Searching
Deletion
Insertion
insert(node, value)
1. If node is null
return new node
2. If value < node.data node.left = insert(node.left, value) 3. Else if value > node.data
node.right = insert(node.right, value)
4. Return node
Searching
search(node, key)
1. If node is null OR node.data == key
return node
2. If key < node.data
search left subtree
3. Else
search right subtree
Deletion
delete(node, key)
1. If node is null
return null
2. If key < node.data
delete from left subtree
3. Else if key > node.data
delete from right subtree
4. Else (node found):
a. If no child → return null
b. If one child → return child
c. If two children:
Find inorder successor
Replace value
Delete successor
Java Code for Binary Search Tree
Run
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class BinarySearchTree {
Node root;
// Insert node
Node insert(Node root, int value) {
if (root == null) {
return new Node(value);
}
if (value < root.data) {
root.left = insert(root.left, value);
} else if (value > root.data) {
root.right = insert(root.right, value);
}
return root;
}
// Search node
boolean search(Node root, int key) {
if (root == null)
return false;
if (root.data == key)
return true;
if (key < root.data)
return search(root.left, key);
else
return search(root.right, key);
}
// Find minimum value node
Node minValue(Node root) {
while (root.left != null)
root = root.left;
return root;
}
// Delete node
Node delete(Node root, int key) {
if (root == null)
return null;
if (key < root.data) {
root.left = delete(root.left, key);
} else if (key > root.data) {
root.right = delete(root.right, key);
} else {
// Case 1: No child
if (root.left == null && root.right == null)
return null;
// Case 2: One child
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
// Case 3: Two children
Node successor = minValue(root.right);
root.data = successor.data;
root.right = delete(root.right, successor.data);
}
return root;
}
// Inorder traversal
void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.root = bst.insert(bst.root, 50);
bst.insert(bst.root, 30);
bst.insert(bst.root, 70);
bst.insert(bst.root, 20);
bst.insert(bst.root, 40);
bst.insert(bst.root, 60);
bst.insert(bst.root, 80);
System.out.print("Inorder Traversal: ");
bst.inorder(bst.root);
System.out.println("\nSearch 40: " + bst.search(bst.root, 40));
bst.root = bst.delete(bst.root, 20);
System.out.print("After Deletion (20): ");
bst.inorder(bst.root);
}
}
Input:
Insert: 50, 30, 70, 20, 40, 60, 80 Search: 40 Delete: 20
Output:
Inorder Traversal: 20 30 40 50 60 70 80 Search 40: true After Deletion (20): 30 40 50 60 70 80
Time Complexity:
Time Complexity for Insertion, Deletion and Search Operations:
Average = O (log n)
Worst Case = O (n)
Average = O (log n)
Worst Case = O (n)
Space Complexity:
Space Complexity for Insertion, Deletion and Search Operations: O(h)
Where: h = height of tree
Where: h = height of tree
Advantages Of BST:
- Inorder Traversal gives sorted order of elements.
- Easy to implement order statistics.
- Helpful in range queries.
Disadvantages Of BST:
- The cost of operations may be high.
- Shape of tree depends on insetions and may be degenerated.
To wrapping up with
The Conditions of BST:
- Duplicate values should be handled properly
- Tree can become skewed (degrades performance)
- Check null before operations
Common problems with Binary Search Tree:
- Ignoring BST property
- Incorrect deletion logic (especially 2 children case)
- Not updating root after deletion
- Infinite recursion due to wrong conditions
Frequently Asked Questions
Answer:
A BST is a binary tree where left child < root < right child.
Answer:
Average case is O(log n), worst case is O(n).
Answer:
It returns elements in sorted order.
Answer:
It returns elements in sorted order.
Answer:
No child, one child, and two children.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
