When I first started learning Data Structures, the Binary Search Tree (BST) felt confusing – left, right, root, traversal, all mixed up! But once I wrote my first simple program, it suddenly made perfect sense.
If you’ve ever felt the same, this tutorial will clear that up. Let’s go step-by-step understand what BST is, how it works, and finally see the Java code that performs Inorder, Preorder, and Postorder traversals.
What’s a Binary Search Tree?
A Binary Search Tree (BST) is a type of binary tree where each node has, at most two children – left and right
- The left child stores smaller values than root
- The right child stores larger values than root
This structure allows for fast searching, insertion, and deletion operations.
Example:
50
/ \
30 70
/ \ / \
20 40 60 80
What Is Tree Traversal?
Traversal means visiting every node in the tree – but how you do it matters. There are 3 main ways:
- Inorder: Left → Root → Right
- Preorder: Root → Left → Right
- Postorder: Left → Right → Root
Each method gives a different order of visiting nodes – and each is useful in its own situation.
Java Code: Binary Search Tree Traversal
Here’s the full code I use when teaching this topic. It’s simple, clean, and beginner-friendly.
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
class BinarySearchTree {
Node root;
void insert(int data) {
root = insertRec(root, data);
}
Node insertRec(Node root, int data) {
if (root == null) return new Node(data);
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}
void preorder(Node node) {
if (node != null) {
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
void postorder(Node node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.print(node.data + " ");
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
int[] values = {50, 30, 20, 40, 70, 60, 80};
for (int val : values) tree.insert(val);
System.out.print("Inorder: ");
tree.inorder(tree.root);
System.out.print("\nPreorder: ");
tree.preorder(tree.root);
System.out.print("\nPostorder: ");
tree.postorder(tree.root);
}
}
Output:
Inorder: 20 30 40 50 60 70 80
Preorder: 50 30 20 40 70 60 80
Postorder: 20 40 30 60 80 70 50