Java binary search trees: insertion, deletion and skew

Java 8+. The program uses only JDK classes and runs without a framework.

The ordering invariant is recursive

A shipment-ID index can descend left or right at every comparison rather than scan every stored ID. Checking only a node against its immediate children is insufficient when validating an arbitrary tree; every descendant must stay within the bounds inherited from its ancestors.

The sample rejects duplicate insertion by returning the existing node. Deletion has three cases. A leaf disappears; a one-child node is replaced by that child; a two-child node takes its successor key from the right subtree and then removes that successor from its old position.

That two-child step matters. Copying the successor key without removing its former node leaves a duplicate behind. Returning replacement roots from the recursive helpers also matters: deleting the root can change the top-level reference. The caller must retain the returned value.

An ordinary tree is not automatically balanced

Ascending insertions can create a chain. Its search behaviour then resembles a linear scan, and recursive helpers can use deep call stacks. A TreeMap or TreeSet may be a better production choice when the application needs ordered lookup rather than a custom teaching tree.

The program owns only integer keys, so copying a successor key is enough. A key/value tree must move the associated value consistently. Mutable object keys require a rule that prevents their ordering fields from changing while stored. Read ordered collection contracts before exposing those keys.

Working program

import java.util.ArrayList;
import java.util.List;
public class ShipmentIdTree {
    static class Entry {
        int shipmentId;
        Entry left, right;
        Entry(int shipmentId) { this.shipmentId = shipmentId; }
    }
    static Entry insert(Entry root, int shipmentId) {
        if (root == null) return new Entry(shipmentId);
        if (shipmentId < root.shipmentId) root.left = insert(root.left, shipmentId);
        else if (shipmentId > root.shipmentId) root.right = insert(root.right, shipmentId);
        return root;
    }
    static Entry delete(Entry root, int shipmentId) {
        if (root == null) return null;
        if (shipmentId < root.shipmentId) root.left = delete(root.left, shipmentId);
        else if (shipmentId > root.shipmentId) root.right = delete(root.right, shipmentId);
        else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            Entry successor = root.right;
            while (successor.left != null) successor = successor.left;
            root.shipmentId = successor.shipmentId;
            root.right = delete(root.right, successor.shipmentId);
        }
        return root;
    }
    static void ordered(Entry root, List<Integer> shipmentIds) {
        if (root == null) return;
        ordered(root.left, shipmentIds);
        shipmentIds.add(root.shipmentId);
        ordered(root.right, shipmentIds);
    }
    public static void main(String[] args) {
        Entry root = null;
        for (int id : new int[]{40, 20, 60, 50, 70}) root = insert(root, id);
        root = delete(root, 40);
        List<Integer> shipmentIds = new ArrayList<>();
        ordered(root, shipmentIds);
        System.out.println(shipmentIds);
    }
}

Output

[20, 50, 60, 70]

Cost and failure boundaries

Insertion and deletion each take O(h) time for height h and use O(h) recursive stack space. A balanced shape gives h around log n; this unbalanced implementation has a worst-case height of n. Stored nodes require O(n) space, and collecting all keys adds O(n) result storage.

The included deletion exercises a two-child root. Add tests for an absent key, a leaf, a one-child node, the only node and repeated deletion. Verify the full in-order sequence after each operation, and separately check that it contains exactly the expected membership; sorted output alone cannot detect a missing key.

Common Mistakes

• Retain the root returned by insertion or deletion.
• Remove the successor from its original subtree after copying its key.
• Do not claim logarithmic worst-case search for an unbalanced tree.