Binary Search Tree — The Data Structures Atlas

Category: Trees

The problem

A sorted array gives O(log n) lookup via binary search, but inserting into the middle costs O(n) to shift everything after it. A linked list gives O(1) insertion but O(n) lookup. Neither gives fast lookup and fast insertion at the same time — and neither can answer "closest key to X" without a scan.

The solution

Keep every node's key greater than everything in its left subtree and smaller than everything in its right subtree. That single invariant is what makes lookup, insertion, and "closest key" queries all able to discard half the remaining tree at every step, the same way binary search does — except the structure itself is what's sorted, not a backing array, so insertion doesn't need to shift anything.

flowchart TD
    N50(("50")) --> N20(("20"))
    N50 --> N80(("80"))
    N20 --> N10(("10"))
    N20 --> N30(("30"))
    N80 --> N70(("70"))
    N80 --> N90(("90"))

Nothing here rebalances. That's the catch: insert order controls the tree's shape. Random insertion order tends toward roughly O(log n) height. Sorted (or reverse-sorted) insertion order degenerates the tree into a straight chain — O(n) height, O(n) lookups, no better than a linked list. The benchmark below measures exactly that gap; a future AVL/Red-Black module in this repo exists specifically to close it by rebalancing on every insert.

Operation	Average (random insert order)	Worst case (sorted insert order)
`get` / `insert` / `delete`	O(log n)	O(n)
`floorEntry` (closest key `<=` X)	O(log n)	O(n)
`inOrderKeys` (sorted traversal)	O(n)	O(n)

Classic example

classic/BinarySearchTree implements insert, get, delete, floorEntry, and in-order traversal from scratch. Delete handles all three textbook cases — leaf, one child, two children (splice in the in-order successor, the smallest key in the right subtree) — without leaving the BST property broken. BinarySearchTreeTest covers all three delete cases plus the degenerate case directly: inserting 100 keys in sorted order and asserting the resulting height is exactly 100.

Applied example: BACEN transaction-limit tier lookup

applied/TransactionLimitTierIndex resolves which BACEN-defined PIX transaction-limit tier applies to a given amount — tiers are defined by threshold ("R$1,000 and above applies until a higher threshold is crossed"), so answering "which tier covers R$1,347.50?" needs an ordered floor lookup, not an exact-match one. This is the operation a hash table structurally cannot offer in better than a full scan; a BST answers it in O(height) by construction. TransactionLimitTierIndexTest covers an amount exactly on a boundary, an amount between two tiers, and an amount below every registered threshold.

Benchmark

./gradlew :trees:binary-search-tree:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Same key set, same lookup operation — the only variable is whether the tree was built from a shuffled or a sorted insertion order.

`get` cost	size=100	size=1,000	size=10,000
random insertion order	18.9 ns	38.7 ns	32.3 ns
sorted insertion order (degenerate)	115.7 ns	1,079.1 ns	22,575.8 ns

The random-order tree's lookup cost stays roughly flat across a 100x size increase — the shape O(log n) predicts. The sorted-order tree's cost grows almost linearly with size instead — going from 1,000 to 10,000 keys (10x the data) makes lookups ~21x slower, consistent with the tree having degenerated into a 10,000-node chain. Same code, same data, only insertion order changed — which is precisely why nothing here rebalances on its own and why that matters.

When not to use it

If insertion order can't be controlled or trusted (sorted or adversarial input), an unbalanced BST degrades to a linked list — see the benchmark above. A self-balancing variant (AVL, Red-Black) is the fix; this repo will add one specifically to contrast against this module.
Only need exact-match lookup, never ordering or range/floor queries? A hash table (see this repo's Hash Table module) gives average O(1) instead of O(log n) for that narrower need.
Need worst-case (not just average-case) guaranteed height? Same answer: a balanced tree.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :trees:binary-search-tree:jacocoTestReport

Report at trees/binary-search-tree/build/reports/jacoco/test/html/index.html.

Unit tests

src/test/java/com/datastructures/trees/binarysearchtree/classic/BinarySearchTreeTest.java

package com.datastructures.trees.binarysearchtree.classic;

import org.junit.jupiter.api.Test;

import java.util.Map;

import static org.assertj.core.api.Assertions.assertThat;

class BinarySearchTreeTest {

    @Test
    void startsEmpty() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();

        assertThat(tree.isEmpty()).isTrue();
        assertThat(tree.size()).isZero();
        assertThat(tree.height()).isZero();
    }

    @Test
    void insertThenGetReturnsTheStoredValue() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();

        tree.insert(50, "root");

        assertThat(tree.get(50)).isEqualTo("root");
        assertThat(tree.contains(50)).isTrue();
        assertThat(tree.isEmpty()).isFalse();
    }

    @Test
    void getOnAMissingKeyReturnsNull() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "root");

        assertThat(tree.get(99)).isNull();
        assertThat(tree.contains(99)).isFalse();
    }

    @Test
    void insertingAnExistingKeyOverwritesItsValue() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "original");

        tree.insert(50, "replaced");

        assertThat(tree.get(50)).isEqualTo("replaced");
        assertThat(tree.size()).isEqualTo(1);
    }

    @Test
    void inOrderKeysAreAlwaysSortedRegardlessOfInsertionOrder() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 50, 70, 80, 90);
    }

    @Test
    void deletingALeafRemovesItAndNothingElse() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "50");
        tree.insert(20, "20");
        tree.insert(80, "80");

        tree.delete(20);

        assertThat(tree.contains(20)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(50, 80);
        assertThat(tree.size()).isEqualTo(2);
    }

    @Test
    void deletingANodeWithOneChildSplicesTheChildIntoItsPlace() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "50");
        tree.insert(20, "20");
        tree.insert(10, "10");

        tree.delete(20);

        assertThat(tree.contains(20)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 50);
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.size()).isEqualTo(2);
    }

    @Test
    void deletingANodeWithTwoChildrenSplicesInTheInOrderSuccessor() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        tree.delete(50);

        assertThat(tree.contains(50)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 70, 80, 90);
        assertThat(tree.size()).isEqualTo(6);
        // The successor (70) must have been spliced up, not just copied and left duplicated.
        assertThat(tree.get(70)).isEqualTo("v70");
    }

    @Test
    void deletingAKeyGreaterThanTheRootDescendsRightBeforeMatching() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        tree.delete(90);

        assertThat(tree.contains(90)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 50, 70, 80);
        assertThat(tree.size()).isEqualTo(6);
    }

    @Test
    void deletingFromAnEmptyTreeIsANoOp() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();

        tree.delete(1);

        assertThat(tree.isEmpty()).isTrue();
    }

    @Test
    void floorEntryReturnsTheExactMatchWhenPresent() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");
        tree.insert(500, "tier-500");

        Map.Entry<Integer, String> floor = tree.floorEntry(500);

        assertThat(floor.getKey()).isEqualTo(500);
        assertThat(floor.getValue()).isEqualTo("tier-500");
    }

    @Test
    void floorEntryReturnsTheLargestKeyNotGreaterThanTheQuery() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");
        tree.insert(500, "tier-500");
        tree.insert(1000, "tier-1000");

        Map.Entry<Integer, String> floor = tree.floorEntry(750);

        assertThat(floor.getKey()).isEqualTo(500);
    }

    @Test
    void floorEntryReturnsNullWhenTheQueryIsBelowEveryStoredKey() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");

        assertThat(tree.floorEntry(50)).isNull();
    }

    @Test
    void sortedInsertionOrderDegeneratesHeightToTheNumberOfNodes() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        for (int key = 0; key < 100; key++) {
            tree.insert(key, "v" + key);
        }

        assertThat(tree.height()).isEqualTo(100);
    }

    @Test
    void randomishInsertionOrderStaysWellBelowTheDegenerateHeight() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] balancedOrder = {50, 25, 75, 12, 37, 62, 87, 6, 18, 31, 43, 56, 68, 81, 93};
        for (int key : balancedOrder) {
            tree.insert(key, "v" + key);
        }

        assertThat(tree.height()).isEqualTo(4);
    }
}

src/test/java/com/datastructures/trees/binarysearchtree/applied/TransactionLimitTierIndexTest.java

package com.datastructures.trees.binarysearchtree.applied;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.math.BigDecimal;
import java.util.Optional;

import static org.assertj.core.api.Assertions.assertThat;

class TransactionLimitTierIndexTest {

    private final TransactionLimitTierIndex index = new TransactionLimitTierIndex();

    @BeforeEach
    void registerBacenTiers() {
        index.registerTier(new TransactionLimitTier(BigDecimal.ZERO, "daytime-standard", BigDecimal.ZERO));
        index.registerTier(new TransactionLimitTier(BigDecimal.valueOf(1000), "daytime-elevated", BigDecimal.valueOf(24)));
        index.registerTier(new TransactionLimitTier(BigDecimal.valueOf(10000), "daytime-high-value", BigDecimal.valueOf(72)));
    }

    @Test
    void amountExactlyOnABoundaryResolvesToThatTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(1000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-elevated");
    }

    @Test
    void amountBetweenTwoBoundariesResolvesToTheLowerTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(5000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-elevated");
    }

    @Test
    void amountAboveTheHighestBoundaryResolvesToTheHighestTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(50000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-high-value");
    }

    @Test
    void amountBelowEveryRegisteredThresholdIsAbsentWhenNoZeroFloorTierExists() {
        TransactionLimitTierIndex indexWithoutZeroFloor = new TransactionLimitTierIndex();
        indexWithoutZeroFloor.registerTier(new TransactionLimitTier(BigDecimal.valueOf(1000), "daytime-elevated", BigDecimal.valueOf(24)));

        Optional<TransactionLimitTier> tier = indexWithoutZeroFloor.tierFor(BigDecimal.valueOf(500));

        assertThat(tier).isEmpty();
    }
}

View full JaCoCo coverage report →