Java Program to Implement Binary Search Tree

A Java program to implement a binary search tree uses a Node class with left and right child references and methods like insert() to add nodes and inorder() to print nodes in sorted order.

Examples

InputInsert 5, 3, 7

OutputInorder traversal: 3 5 7

InputInsert 10, 5, 15, 3, 7

OutputInorder traversal: 3 5 7 10 15

InputInsert 8

OutputInorder traversal: 8

How to Think About It

To build a binary search tree, start with an empty root. For each new value, compare it with the current node's value. If smaller, go left; if larger, go right. Insert the new node where a child is missing. This keeps the tree sorted for easy searching and traversal.

Algorithm

1

Create a Node class with data, left, and right pointers.

2

Start with an empty root node.

3

For each value to insert, compare it with the current node's data.

4

If value is less, move to left child; if more, move to right child.

5

Insert the new node where a child pointer is null.

6

To display, perform inorder traversal: left subtree, node, right subtree.

Code

java

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BST {
    Node root;

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        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() {
        inorderRec(root);
        System.out.println();
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.inorder();
    }
}

Output

3 5 7 

Dry Run

Let's trace inserting 5, 3, 7 into the BST and then printing inorder.

1

Insert 5

Root is null, create new node with data 5 as root.

2

Insert 3

3 < 5, go left of root which is null, insert node with data 3 there.

3

Insert 7

7 > 5, go right of root which is null, insert node with data 7 there.

4

Inorder traversal

Visit left subtree (3), root (5), right subtree (7), print in order: 3 5 7

Step	Current Node	Action
Insert 5	null	Create root node with 5
Insert 3	5	3 < 5, go left, insert 3
Insert 7	5	7 > 5, go right, insert 7
Inorder	root	Print 3 5 7

Why This Works

Step 1: Node Structure

Each Node holds a value and references to left and right children, allowing the tree to branch.

Step 2: Insertion Logic

Insert compares the new value with current node's data and decides to go left or right, maintaining sorted order.

Step 3: Inorder Traversal

Inorder visits left child, node, then right child, printing values in ascending order.

Alternative Approaches

Iterative Insertion

java

class Node {
    int data;
    Node left, right;
    Node(int data) { this.data = data; left = right = null; }
}

public class BSTIterative {
    Node root;

    void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
            return;
        }
        Node current = root, parent = null;
        while (current != null) {
            parent = current;
            if (data < current.data) current = current.left;
            else if (data > current.data) current = current.right;
            else return; // no duplicates
        }
        if (data < parent.data) parent.left = newNode;
        else parent.right = newNode;
    }

    void inorder() {
        inorderRec(root);
        System.out.println();
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BSTIterative tree = new BSTIterative();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.inorder();
    }
}

Iterative insertion avoids recursion but is slightly more complex to write.

Using Java Collections TreeSet

java

import java.util.TreeSet;

public class BSTWithTreeSet {
    public static void main(String[] args) {
        TreeSet<Integer> tree = new TreeSet<>();
        tree.add(5);
        tree.add(3);
        tree.add(7);
        for (int val : tree) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

TreeSet is a built-in balanced tree, simpler but less control over structure.

Complexity: O(h) time, O(h) space

Time Complexity

Insertion and search take O(h) time where h is tree height; balanced trees have h = O(log n), worst case is O(n).

Space Complexity

Recursive insertion uses O(h) stack space; iterative insertion uses O(1) extra space.

Which Approach is Fastest?

Recursive insertion is simpler but iterative uses less memory; built-in TreeSet is fastest for balanced trees but less flexible.

Approach	Time	Space	Best For
Recursive Insertion	O(h)	O(h)	Simple code, small trees
Iterative Insertion	O(h)	O(1)	Memory efficient, larger trees
Java TreeSet	O(log n)	O(n)	Quick balanced tree with no manual code