Binary trees / anatomy, ADT, and deletion / interactive
Everything hangs off a single node
A binary tree is the smallest interesting data structure: one value, a left child, a right child — and both of those children are trees again. That self-reference is the whole trick, and it's why the methods below are three lines long. We start with the anatomy and the ADT, build each operation one step at a time, then add an ordering rule to get a binary search tree — where deleting a node turns out to be the one genuinely awkward thing to do.
Edited Aug 7, 2026 · 10:37 AM ADT
What a binary tree is
A value, a left child, a right child — and both of those children are themselves binary trees. The definition refers to itself, which is why nearly every method on this page is recursive.
Ordered lookup
Sets and maps that stay sorted:TreeMap, database indexes, anything that needs range queries. That's what the second half of this page is about.Parsing
An expression likea * (b + c) becomes a tree with operators at the branches and values at the leaves. Evaluating it is one recursive walk.Priority queues
A binary heap is a binary tree with a weaker rule — every node beats its children — which is enough to pull the smallest item in O(log n).Compression
Huffman coding builds a tree where the path down to a leaf is the bit pattern for that symbol.The ADT contract
Seven operations. Note the shape of insert: this is a general binary tree, so you name the parent and the side yourself — there is no ordering rule to place the node for you, and therefore no need for a Comparable bound on T.
| Method | Cost | What it has to do |
|---|---|---|
| insertRoot(T item) | O(1) | Creates the very first node. Returns false if a root already exists, so it can't be used to overwrite the tree. |
| insert(T parent, T item, ChildPosition side) | O(n) | Finds parent, then hangs the new node on the named side. If that slot is taken, the existing child is displaced downward rather than overwritten. O(n) because finding the parent is a full search. |
| T contains(T item) | O(n) | Returns the stored item whose equals matches, or null. Depth-first pre-order walk — no ordering invariant means no shortcut, so a miss visits every node. |
| remove(T item) | O(n) | Three cases by child count. The two-child case copies the in-order successor's value up and deletes the duplicate below. |
| size() | O(1) | Return the maintained counter. Increment in both inserts, decrement in remove — and only on the paths that actually change the tree. |
| height() | O(n) | Recursive: 1 + max(left, right), counting edges — so a single node is 0 and an empty tree is -1. Must visit everything, so no counter shortcut. |
| String print() | O(n) | In-order traversal as a space-separated string, built with StringBuilder — the no-Collections constraint rules out gathering into a list first. |
Operations, step by step
A five-node tree with no ordering rule — just values hung where we put them. Pick an operation, then Run it or press Step to advance one line at a time.
BinaryTreeADT<T> the corrected contract
The nested node class
Traversal — the move underneath every operation
Every op above is a recursive walk. Watch a call push a frame, park its bookmark, dive into a child, and resume on the very next line when the child returns. Swap the mode to see how one line's position changes the visit order.
The code A · B · C mark the pause points
Call stack 0 frames
Adding an ordering rule
Everything so far works on any binary tree. One extra constraint turns it into something you can actually search.
A binary search tree adds a single invariant: for every node, every value in its left subtree is smaller and every value in its right subtree is larger. Not just the immediate children — the whole subtree, all the way down.
That one rule pays for itself immediately. contains stops being an exhaustive walk: at each node you compare once and discard half of what remains. On the thirty-node tree below that is at most six comparisons instead of thirty. It also gives you sorted output for free, since an in-order traversal is just the invariant restated.
This is also where Comparable finally earns its place. The general tree only needed equals, because you told it where to put things. A BST decides for itself, so it needs to know which of two values is larger.
The bill arrives at remove. In a general tree you can rearrange nodes however you like. In a BST every replacement has to keep the invariant true for every ancestor above it — which is what makes deletion the one operation with real cases to think about.
A binary search tree, live
Thirty nodes, six levels deep. Click any node to delete it and watch the pointers get rewired — or use the toolbar, which stays pinned while you scroll the tree.
Click any node to delete it. Detail view pans to follow the search; Fit shows the whole shape at once.
Step log
The three cases
Once you have found the node, how you remove it depends entirely on how many children it has. Only the last case is genuinely interesting. Each diagram runs on its own.
Where case 3 gets awkward
Four variants that trip people up. Run each one and watch the assignment list on the right tick over as the animation reaches it — swap two of them and you lose half the tree.
BST reference code
The BST versions of insert, search and delete, for reference. Lines light up while the tree above animates, so you can see which branch is executing.
Cost
Deletion isO(h) — the height of the tree. Balanced, that's O(log n); a tree built from sorted input degrades to a linked list and O(n). The tree above is height 6 for 30 nodes; a perfectly balanced one would be 5.