Building a Binary Search Tree (BST) in Java: Recursive Operations & Range Queries

Suppose you are building an online auction platform. Bids arrive continuously in random order. Your system needs to answer two questions instantly at any given millisecond:

1. What is the current highest bid?
2. What are all active bids between $100 and $500 in sorted order?

If you store incoming bids inside an unsorted ArrayList, finding the highest bid requires scanning every element in $O(N)$ linear time. If you keep the array sorted on every insert, shifting elements takes $O(N)$ time per new bid.

If you store bids in a HashMap, finding items within a range ($100 to $500) requires iterating through every bucket because hash functions destroy item ordering.

This is why trees exist. A Binary Search Tree (BST) keeps data sorted while allowing $O(\log N)$ insertions, removals, and searches.

---

The Binary Search Tree Invariant

A Binary Search Tree consists of connected node objects. Every node holds a value and up to two child references: left and right.

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

The BST invariant enforces a simple ordering rule across every node in the tree:

• Every node in the left subtree has a value strictly smaller than the parent node (left.value < parent.value).
• Every node in the right subtree has a value strictly larger than or equal to the parent node (right.value >= parent.value).

Because of this rule, searching for a value eliminates half of the remaining tree branches at every step.

---

Searching in $O(\log N)$ Time

Tracing a search for 60 in the binary search tree above illustrates the $\mathcal{O}(\log N)$ path:

1. Start at root 50. Since $60 > 50$, discard the entire left subtree ($[30, 20, 40]$). Move right to 70.
2. Compare $60$ with 70. Since $60 < 70$, move left to 60.
3. Match found in 3 steps instead of scanning 7 elements.

$\text{Steps for 1,000,000 items} \approx \log_2(1,000,000) \approx 20 \text{ comparisons}$

---

Step-by-Step BST Implementation

public class MyBinarySearchTree<K extends Comparable<K>> {
    static class Node<K> {
        K key;
        Node<K> left;
        Node<K> right;

        Node(K key) {
            this.key = key;
        }
    }

    private Node<K> root;
    private int size = 0;

    public void add(K key) {
        if (key == null) throw new NullPointerException("Null keys not supported");
        root = insertRecursive(root, key);
    }

    private Node<K> insertRecursive(Node<K> current, K key) {
        if (current == null) {
            size++;
            return new Node<>(key);
        }

        int cmp = key.compareTo(current.key);
        if (cmp < 0) {
            current.left = insertRecursive(current.left, key);
        } else if (cmp > 0) {
            current.right = insertRecursive(current.right, key);
        }
        // Duplicate keys ignored in standard BST set
        return current;
    }

    public boolean contains(K key) {
        return searchRecursive(root, key);
    }

    private boolean searchRecursive(Node<K> current, K key) {
        if (current == null) return false;

        int cmp = key.compareTo(current.key);
        if (cmp == 0) return true;
        return cmp < 0 
            ? searchRecursive(current.left, key) 
            : searchRecursive(current.right, key);
    }

    public int size() {
        return size;
    }
}

---

In-Order Traversal: Extracting Sorted Data

How do you extract elements from a BST in perfect sorted order?

By running an in-order traversal (left -> root -> right).

public void printInOrder() {
    inOrderRecursive(root);
}

private void inOrderRecursive(Node<K> node) {
    if (node != null) {
        inOrderRecursive(node.left);
        System.out.print(node.key + " ");
        inOrderRecursive(node.right);
    }
}

For the tree above, printInOrder() visits nodes in exact ascending order: 20 30 40 50 60 70 80.

---

The Degenerate Tree Flaw

Suppose items arrive in already-sorted order: 10, 20, 30, 40, 50.

  [ 10 ]
        \
         [ 20 ]
               \
                [ 30 ]
                      \
                       [ 40 ]
                             \
                              [ 50 ]

Without balancing mechanisms, the BST collapses into a singly linked list. Search performance degrades from $O(\log N)$ down to $O(N)$ linear time.

To fix this flaw, production engines use self-balancing trees like Red-Black Trees.

---

Quick Summary

• Binary Search Trees maintain sorted ordering by placing smaller items left and larger items right.
• Range searches and in-order traversals run efficiently because data remains structured.
• Inserting pre-sorted data causes naive BSTs to degrade into $O(N)$ linked chains, creating the need for self-balancing rotations.

References & Further Reading

1. Lea, D. (2000). Concurrent Programming in Java: Design Principles and Patterns (2nd Edition). Addison-Wesley.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.Vector & java.util.Hashtable. GitHub.
3. Bloch, J. (2018). Effective Java (3rd Edition) — Item 81: Prefer Concurrency Utilities to Synchronized Collections. Addison-Wesley.

---