Binary Search Tree (BST) in Data Structures

December 24, 2025

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 &lt; 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.

data structures

CoderMantra