Skip to main content

Implementing Binary Search Tree in Java

A Binary Search Tree (BST) is a node-based binary tree data structure where each node stores a key, and every node in the left subtree holds a key strictly smaller than the parent, while every node in the right subtree holds a key strictly greater. This ordering property makes BSTs excellent for fast lookup, insertion, and deletion — all in O(log n) time on average.

In this post, we implement a BST in Java that supports insertion, search, and three traversal orders: inorder, preorder, and postorder.

BST Properties

  • One node is designated the root of the tree.
  • Each internal node contains a key and has at most two child subtrees.
  • The left subtree of a node contains only keys strictly less than the node’s key.
  • The right subtree of a node contains only keys strictly greater than the node’s key.
  • Each subtree is itself a valid BST.

Java Program: Binary Search Tree

import java.io.*;

// Represents a single node in the BST
class BSTNode {
    int data;
    BSTNode left, right;

    public BSTNode(int value) {
        data = value;
        left = null;   // No left child initially
        right = null;  // No right child initially
    }
}

// Binary Search Tree with insert, search, and traversal operations
class BST {
    BSTNode root;  // Root node of the tree

    // Public method to insert a value into the BST
    public void insert(int value) {
        if (root == null) {
            root = new BSTNode(value);  // First insertion becomes root
        } else {
            insertRecursive(root, value);
        }
    }

    // Recursively finds the correct position and inserts
    private void insertRecursive(BSTNode current, int value) {
        if (current.data == value) {
            System.out.println("Value already present in tree");
            return;
        } else if (value < current.data) {
            // Go left if value is smaller
            if (current.left == null) {
                current.left = new BSTNode(value);
            } else {
                insertRecursive(current.left, value);
            }
        } else {
            // Go right if value is larger
            if (current.right == null) {
                current.right = new BSTNode(value);
            } else {
                insertRecursive(current.right, value);
            }
        }
    }

    // Inorder traversal: Left → Root → Right (produces sorted output)
    public void printInorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        inorderRecursive(root);
        System.out.println();
    }

    private void inorderRecursive(BSTNode node) {
        if (node != null) {
            inorderRecursive(node.left);
            System.out.print(node.data + " ");
            inorderRecursive(node.right);
        }
    }

    // Preorder traversal: Root → Left → Right
    public void printPreorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        preorderRecursive(root);
        System.out.println();
    }

    private void preorderRecursive(BSTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorderRecursive(node.left);
            preorderRecursive(node.right);
        }
    }

    // Postorder traversal: Left → Right → Root
    public void printPostorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        postorderRecursive(root);
        System.out.println();
    }

    private void postorderRecursive(BSTNode node) {
        if (node != null) {
            postorderRecursive(node.left);
            postorderRecursive(node.right);
            System.out.print(node.data + " ");
        }
    }

    // Search for a value in the BST
    public void search(int value) {
        searchRecursive(root, value);
    }

    private void searchRecursive(BSTNode node, int value) {
        if (node == null) {
            System.out.println("Data not found");
            return;
        }
        if (node.data == value) {
            System.out.println("Data found");
        } else if (value < node.data) {
            searchRecursive(node.left, value);   // Search left subtree
        } else {
            searchRecursive(node.right, value);  // Search right subtree
        }
    }
}

public class BSTDemo {
    public static void main(String[] args) throws IOException {
        BST tree = new BST();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int choice;

        do {
            System.out.println();
            System.out.println("--- Binary Search Tree Menu ---");
            System.out.println("1. Insert element");
            System.out.println("2. Display Inorder (sorted)");
            System.out.println("3. Display Preorder");
            System.out.println("4. Display Postorder");
            System.out.println("5. Search element");
            System.out.println("6. Exit");
            System.out.print("Enter option: ");
            choice = Integer.parseInt(reader.readLine());

            switch (choice) {
                case 1:
                    System.out.print("Enter element to insert: ");
                    int insertValue = Integer.parseInt(reader.readLine());
                    tree.insert(insertValue);
                    break;
                case 2:
                    System.out.print("Inorder: ");
                    tree.printInorder();
                    break;
                case 3:
                    System.out.print("Preorder: ");
                    tree.printPreorder();
                    break;
                case 4:
                    System.out.print("Postorder: ");
                    tree.printPostorder();
                    break;
                case 5:
                    System.out.print("Enter element to search: ");
                    int searchValue = Integer.parseInt(reader.readLine());
                    tree.search(searchValue);
                    break;
                case 6:
                    System.out.println("Exiting...");
                    break;
                default:
                    System.out.println("Invalid option");
            }
        } while (choice != 6);
    }
}

How the Code Works

  1. BSTNode class — Holds an integer data field plus left and right child references, both initially null.
  2. insert() — If the tree is empty, the value becomes the root. Otherwise, insertRecursive() navigates left for smaller values and right for larger ones until a null slot is found.
  3. Inorder traversal — Visits left → root → right. Because of the BST property, inorder traversal always produces keys in ascending sorted order.
  4. Preorder traversal — Visits root → left → right. Useful for creating a copy of the tree.
  5. Postorder traversal — Visits left → right → root. Useful for deleting or freeing the tree bottom-up.
  6. search() — Compares the target value with the current node and recursively narrows the search to the left or right subtree, achieving O(log n) on a balanced tree.

Sample Output

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 2
Inorder: Inorder: 10 13 15 17 21 24 

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 3
Preorder: Preorder: 17 13 10 15 21 24 

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 4
Postorder: Postorder: 10 15 13 24 21 17 

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 5
Enter element to search: 15
Data found

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 5
Enter element to search: 99
Data not found

--- Binary Search Tree Menu ---
1. Insert element
2. Display Inorder (sorted)
3. Display Preorder
4. Display Postorder
5. Search element
6. Exit
Enter option: 6
Exiting...

We insert the values 17, 13, 21, 10, 15, 24 in sequence, building the following BST structure:

        17
       /  
      13   21
     /      
    10  15   24

Output Explanation

  • Inorder (10 13 15 17 21 24) — Produces the keys in sorted ascending order, confirming the BST property is maintained.
  • Preorder (17 13 10 15 21 24) — Starts with the root (17), then recursively visits each left subtree before the right.
  • Postorder (10 15 13 24 21 17) — Visits all children before their parent; the root (17) is always last.
  • Search for 15 — Starts at 17, goes left to 13 (15 > 13), goes right to 15 — found in 3 comparisons.
  • Search for 99 — Reaches a null node without finding the value, so “Data not found” is printed.

See Also

Conclusion

Binary Search Trees provide an elegant way to maintain a dynamically sorted collection of elements. The three traversal orders — inorder, preorder, and postorder — each serve different practical purposes, from producing sorted output to tree copying and deletion. As a next step, consider implementing BST deletion (the trickiest operation) or exploring self-balancing trees like AVL trees that guarantee O(log n) performance even in the worst case.

No Comments yet!

This site uses Akismet to reduce spam. Learn how your comment data is processed.