A Binary Search Tree (BST) is a special type of Binary Tree. In a BST, data is stored in a sorted way using a simple rule.
Binary Search Tree (BST) Rule
This rule defines a Binary Search for every node in a BST:
- All values in the left subtree are smaller
- All values in the right subtree are greater
Example of a BST
Suppose we insert these values in a Binary Search Tree:
50, 30, 70, 20, 40, 60, 80. The BST will look like this:
50
/ \
30 70
/ \ / \
20 40 60 80
Notice: Left side values are smaller, Right side values are larger
Why Do We Use BST?
BST is used because it makes searching faster. Instead of checking every element (like arrays), BST skips half of the tree, moves left or right based on value. This makes operations efficient. BST helps in:
- Fast searching
- Fast insertion
- Fast deletion
- Maintaining sorted data
BST Traversal
- Inorder Traversal: Left → Root → Right
- Preorder Traversal: Root → Left → Right
- Postorder Traversal: Left → Right → Root
Binary Search Tree Program in Java
A Binary Search Tree is a binary tree where data is stored in a sorted way. In this Java program, we insert values into a BST and print them using inorder, preorder, and postorder traversals. This Java example helps beginners understand how searching and sorting work inside trees.
// Node class
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
// Binary Search Tree class
public class BinarySearchTree {
Node root;
// Insert a value into BST
public void insert(int value) {
root = insertRec(root, value);
}
// Recursive insert method
private Node insertRec(Node root, int value) {
// If tree is empty
if (root == null) {
return new Node(value);
}
// If value is smaller, go left
if (value < root.data) {
root.left = insertRec(root.left, value);
}
// If value is greater, go right
else if (value > root.data) {
root.right = insertRec(root.right, value);
}
// Return unchanged root
return root;
}
// Inorder Traversal
public void inorder(Node root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Preorder Traversal
public void preorder(Node root) {
if (root == null)
return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Postorder Traversal
public void postorder(Node root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
// Main method
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert values
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.print("Inorder Traversal: ");
bst.inorder(bst.root); // 20 30 40 50 60 70 80
System.out.print("\nPreorder Traversal: ");
bst.preorder(bst.root); // 50 30 20 40 70 60 80
System.out.print("\nPostorder Traversal: ");
bst.postorder(bst.root); // 20 40 30 60 80 70 50
}
}
How BST Insertion Works
If the tree is empty, the first value becomes the root. If the next value is smaller, go left; if greater, go right.
Mini Quiz
Mini Project
Mini Project: Library Book ID Management using Binary Search Tree
Question:
A library stores book IDs in a Binary Search Tree (BST) so that they remain organized in sorted order.
Create a Java program to:
- Insert book IDs into the Binary Search Tree.
- Display all book IDs using Inorder Traversal.
- Display all book IDs using Preorder Traversal.
- Display all book IDs using Postorder Traversal.
View Answer Code
// Node class
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
// Library Book BST
public class LibraryBookBST {
Node root;
// Insert book ID
public void insert(int value) {
root = insertRec(root, value);
}
// Recursive insert
private Node insertRec(Node root, int value) {
if (root == null) {
return new Node(value);
}
if (value < root.data) {
root.left = insertRec(root.left, value);
}
else if (value > root.data) {
root.right = insertRec(root.right, value);
}
return root;
}
// Inorder Traversal
public void inorder(Node root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Preorder Traversal
public void preorder(Node root) {
if (root == null)
return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Postorder Traversal
public void postorder(Node root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
LibraryBookBST library = new LibraryBookBST();
library.insert(500);
library.insert(300);
library.insert(700);
library.insert(200);
library.insert(400);
library.insert(600);
library.insert(800);
System.out.print("Inorder Traversal: ");
library.inorder(library.root);
System.out.print("\nPreorder Traversal: ");
library.preorder(library.root);
System.out.print("\nPostorder Traversal: ");
library.postorder(library.root);
}
}
Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.
Shubhranshu Shekhar is a coding instructor, mentor, and founder of VSIT Delhi with 20+ years of teaching experience (since 2004). He has guided many students who are now working in multinational companies and specializes in Full Stack Development, Python, Digital Marketing, and Data Analytics.