Binary Search Trees from scratch
Build a BST, understand insert and search, and see why balance is everything.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
The invariant
For every node in a BST, every key in the left subtree is strictly smaller, and every key in the right subtree is strictly larger. That single rule lets contains halve the search space at each step — the same logic as binary search on a sorted array, but with insertions and deletions still O(log n).
Insert
Walk down from the root, going left when the new key is smaller, right when larger. Attach a fresh node at the first null child you find. Duplicates are typically ignored — if you need to count occurrences, store a counter on the node.
Search and traversals
contains is a plain iterative walk. An *in-order* traversal (left, node, right) visits keys in sorted order — that's how BSTs give you sorted iteration for free. *Pre-order* and *post-order* are useful for serialization and cleanup.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Deletion is the tricky one
Removing a leaf is trivial. Removing a node with one child is easy — splice the child in. Removing a node with two children requires finding the in-order successor (the smallest key in the right subtree), copying its value into the node being deleted, and then deleting the successor from the right subtree.
Balance matters
The theoretical O(log n) assumes the tree is balanced. Insert keys in sorted order into a plain BST and you build a linked list — O(n) per operation. Self-balancing variants (AVL, red-black, splay) rebalance on every insert or delete. Java's TreeMap is a red-black tree, so in production you almost never write a raw BST — you use TreeMap.
When to build your own
For teaching, for problems that need a custom augmentation (e.g., storing subtree sums for order statistics), and for interview practice. For any production data structure need in Java, reach for TreeMap or TreeSet first.