Binary Search Tree — Data Structure & Algrorithm

Imagine you have a collection of numbers and want to search for a particular number quickly.

If the numbers are stored randomly:

50, 20, 80, 10, 30, 60, 90

you may need to check many elements.

But what if we organize them in a special tree where smaller values always go to the left and larger values always go to the right?

That's a Binary Search Tree, or BST.

A Binary Search Tree is a special type of binary tree designed to make searching, insertion, and deletion more efficient.

What is a Binary Search Tree?

A Binary Search Tree is a binary tree that follows this rule:

Left Subtree < Node < Right Subtree

For example:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

For the root 50:

Values smaller than 50 → Left
Values larger than 50 → Right

The same rule applies recursively to every node.

For node 30:

20 < 30 < 40

For node 70:

60 < 70 < 80

That's what makes this tree a Binary Search Tree.

Binary Tree vs Binary Search Tree

This distinction is extremely important.

A Binary Tree only requires:

Each node can have at most two children.

For example:

        50
       /  \
      80   20

This is a valid binary tree.

But it is not a Binary Search Tree because 80 is on the left of 50, even though 80 > 50.

A BST must follow:

Smaller → Left
Larger  → Right

So:

Binary Tree
       ↓
At most 2 children

BST
       ↓
At most 2 children
+
Ordering rule

Creating a BST Node in Java

A BST node looks similar to a normal binary tree node:

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

Each node contains:

data
left
right

Building a Binary Search Tree

Suppose we insert these values:

50, 30, 70, 20, 40, 60, 80

Start with 50:

Insert 30.

Since:

30 < 50

it goes to the left:

    50
   /
  30

Insert 70.

Since:

70 > 50

it goes to the right:

    50
   /  \
  30   70

Insert 20:

20 < 50
20 < 30

So it goes to the left of 30:

Insert 40:

40 < 50
40 > 30

So:

After inserting all values:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

Searching in a BST

This is where the BST becomes powerful.

Suppose we want to find 60.

Start at the root:

Compare:

60 > 50

So we don't need to search the entire left subtree.

We go right:

Now:

60 < 70

So we go left:

Found it.

The search path was:

50 → 70 → 60

We didn't have to check:

30, 20, 40, 80

This is the main advantage of the BST ordering rule.

Searching in Java

We can write a recursive search method:

static boolean search(Node root, int value) {

    if (root == null) {
        return false;
    }

    if (root.data == value) {
        return true;
    }

    if (value < root.data) {
        return search(root.left, value);
    }

    return search(root.right, value);
}

The logic is:

Value == Node?
     ↓
    Yes → Found

Value < Node?
     ↓
   Search Left

Value > Node?
     ↓
  Search Right

Inserting into a BST

To insert a value, we follow the same comparison process.

Suppose our tree is:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

We want to insert 35.

Start at 50:

35 < 50

Go left to 30.

35 > 30

Go right to 40.

35 < 40

Go left.

The position is empty, so 35 is inserted there:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80
         /
        35

Java Insertion

We can implement insertion recursively:

static Node insert(Node root, int value) {

    if (root == null) {
        return new Node(value);
    }

    if (value < root.data) {
        root.left = insert(root.left, value);
    }
    else if (value > root.data) {
        root.right = insert(root.right, value);
    }

    return root;
}

Notice that if the value is equal to an existing value, this implementation does nothing.

That's one possible BST policy. Other implementations may allow duplicates using a specific rule.

Creating a BST in Java

We can use the insert() method to build a complete BST:

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static Node insert(Node root, int value) {

        if (root == null) {
            return new Node(value);
        }

        if (value < root.data) {
            root.left = insert(root.left, value);
        }
        else if (value > root.data) {
            root.right = insert(root.right, value);
        }

        return root;
    }

    public static void main(String[] args) {

        Node root = null;

        root = insert(root, 50);
        root = insert(root, 30);
        root = insert(root, 70);
        root = insert(root, 20);
        root = insert(root, 40);
        root = insert(root, 60);
        root = insert(root, 80);
    }
}

This produces:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

Inorder Traversal of a BST

Here's a very important property of a Binary Search Tree:

Inorder traversal of a BST produces the values in sorted order.

Consider:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

Inorder means:

Left → Root → Right

The result is:

20 → 30 → 40 → 50 → 60 → 70 → 80

Notice that the values are sorted.

This is one of the most important facts to remember about BSTs.

Finding the Minimum Value

In a BST, the smallest value is always found by continuously going left.

For:

keep moving left:

50 → 30 → 20

So 20 is the minimum.

Java:

static Node findMin(Node root) {

    while (root.left != null) {
        root = root.left;
    }

    return root;
}

Finding the Maximum Value

The largest value is found by continuously going right.

For:

we follow:

50 → 70 → 80

So 80 is the maximum.

Java:

static Node findMax(Node root) {

    while (root.right != null) {
        root = root.right;
    }

    return root;
}

Deleting a Node

Deletion is one of the most important and slightly more complicated BST operations.

There are three main cases.

Case 1 → Node has no children
Case 2 → Node has one child
Case 3 → Node has two children

Case 1: Leaf Node

Suppose we want to delete 20:

20 has no children.

We can simply remove it:

       50
      /
     30

This is the easiest case.

Case 2: One Child

Suppose we have:

If we delete 30, it has one child: 40.

We connect its parent directly to 40:

       50
      /
     40

The child takes the deleted node's position.

Case 3: Two Children

This is the most interesting case.

Suppose we want to delete 50:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

50 has two children.

We can replace it with its inorder successor, which is the smallest value in the right subtree.

The right subtree is:

       70
      /  \
     60   80

The smallest value is 60.

So we replace 50 with 60:

          60
         /  \
        30   70
       / \    \
      20 40    80

The other common approach is to use the inorder predecessor, which is the largest value in the left subtree.

Java Deletion

A recursive implementation can handle all three cases:

static Node delete(Node root, int value) {

    if (root == null) {
        return null;
    }

    if (value < root.data) {

        root.left = delete(root.left, value);

    }
    else if (value > root.data) {

        root.right = delete(root.right, value);

    }
    else {

        // No child
        if (root.left == null && root.right == null) {
            return null;
        }

        // Only right child
        if (root.left == null) {
            return root.right;
        }

        // Only left child
        if (root.right == null) {
            return root.left;
        }

        // Two children
        Node successor = findMin(root.right);

        root.data = successor.data;

        root.right = delete(
            root.right,
            successor.data
        );
    }

    return root;
}

The important thing is not to memorize the entire code immediately. First understand the three deletion cases.

Time Complexity

The performance of a BST depends heavily on its height.

For a balanced BST:

Search   → O(log n)
Insert   → O(log n)
Delete   → O(log n)

Why?

Because each comparison allows us to eliminate roughly half of the remaining search space.

But consider this tree:

This tree is essentially a linked list.

In this situation:

Search   → O(n)
Insert   → O(n)
Delete   → O(n)

So the shape of the tree matters enormously.

Balanced vs Unbalanced BST

A balanced BST:

          50
        /    \
       30     70
      /  \   /  \
     20  40 60  80

has a relatively small height.

An unbalanced BST:

has a large height compared with the number of nodes.

That's why advanced data structures such as AVL Trees and Red-Black Trees were developed. They help keep search trees balanced.

BST vs HashMap

Both can provide fast lookup, but they work differently.

A HashMap uses hashing:

Key
 ↓
Hash
 ↓
Value

A BST uses ordering:

Value < Node → Left
Value > Node → Right

A major advantage of a BST is that its elements have an inherent sorted structure.

For example, inorder traversal gives:

10 → 20 → 30 → 40 → 50

A normal HashMap does not maintain its keys in sorted order.

BST Applications

Binary Search Trees are useful for:

Searching sorted data
Maintaining dynamic sorted data
Finding minimum and maximum values
Finding predecessor and successor
Range queries
Maintaining ordered collections
Implementing ordered sets and maps

Balanced variants are especially useful when we need predictable performance.

Real-Life Example

Imagine a dictionary where words are arranged according to alphabetical order.

Instead of checking every word, we can compare the word we're searching for with the current word.

If the target comes alphabetically before it:

Go Left

If it comes after:

Go Right

This is conceptually similar to how a Binary Search Tree narrows down the search.

A Complete Example

Here's a simple BST that supports insertion and searching:

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static Node insert(Node root, int value) {

        if (root == null) {
            return new Node(value);
        }

        if (value < root.data) {
            root.left = insert(root.left, value);
        }
        else if (value > root.data) {
            root.right = insert(root.right, value);
        }

        return root;
    }

    static boolean search(Node root, int value) {

        if (root == null) {
            return false;
        }

        if (root.data == value) {
            return true;
        }

        if (value < root.data) {
            return search(root.left, value);
        }

        return search(root.right, value);
    }

    static void inorder(Node root) {

        if (root == null) {
            return;
        }

        inorder(root.left);
        System.out.print(root.data + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {

        Node root = null;

        root = insert(root, 50);
        root = insert(root, 30);
        root = insert(root, 70);
        root = insert(root, 20);
        root = insert(root, 40);
        root = insert(root, 60);
        root = insert(root, 80);

        System.out.print("Inorder: ");
        inorder(root);

        System.out.println();

        System.out.println(
            "60 exists: " + search(root, 60)
        );

        System.out.println(
            "90 exists: " + search(root, 90)
        );
    }
}

Output:

Inorder: 20 30 40 50 60 70 80
60 exists: true
90 exists: false

The Main Idea

A Binary Search Tree is a special type of binary tree where every node follows:

Left Subtree < Node < Right Subtree

For example:

          50
         /  \
        30   70
       / \   / \
      20 40 60 80

The most important operations are:

Search
Insert
Delete
Find Minimum
Find Maximum

And remember the three deletion cases:

0 children → Remove directly
1 child   → Replace with the child
2 children → Replace using successor/predecessor

The most important performance fact is:

Balanced BST:
Search → O(log n)
Insert → O(log n)
Delete → O(log n)

But an unbalanced BST can degrade to:

O(n)

A Binary Search Tree uses the ordering of its nodes to make searching, insertion, and deletion efficient, with smaller values on the left and larger values on the right.