Step by step
The example above, written out — the same steps the animation plays.
- 1An empty tree. In a binary search tree, everything in a node's left subtree is smaller and everything on the right is bigger.
- 2Insert 50. 50 becomes the root.
- 3Insert 30: compare with 50. 30 < 50: go left.
- 430 placed. The left spot under 50 is free: 30 goes there.
- 5Insert 70: compare with 50. 70 > 50: go right.
- 670 placed. The right spot under 50 is free: 70 goes there.
- 7Insert 20: compare with 50. 20 < 50: go left.
- 8Insert 20: compare with 30. 20 < 30: go left.
- 920 placed. The left spot under 30 is free: 20 goes there.
- 10Insert 40: compare with 50. 40 < 50: go left.
- 11Insert 40: compare with 30. 40 > 30: go right.
- 1240 placed. The right spot under 30 is free: 40 goes there.
- 13Insert 60: compare with 50. 60 > 50: go right.
- 14Insert 60: compare with 70. 60 < 70: go left.
…and 8 more steps — press Play above to watch them all.
What's happening?
- To insert, start at the root and go left for smaller, right for bigger, until there is a free spot.
- Searching follows the same path; each step rules out a whole subtree.
- An in-order walk (left, node, right) visits the values in sorted order.
Complexity
- Time
- O(log n) search and insert when balanced · O(n) when it degrades to a list
- Space
- O(n)
Where you'll meet it
Database indexes (as B-trees), ordered maps and sets (Java's TreeMap), file systems and autocomplete over sorted keys.
Common mistake
Inserting already-sorted values: every value goes right and the "tree" becomes a list. Self-balancing trees (red-black, AVL) prevent this.
FAQ
Why does sorted input make a bad tree?
Each new value is bigger than all the others, so it always goes to the far right — try the "Sorted input" button.
What is a balanced tree?
One whose height stays around log n, so searches stay fast. Red-black and AVL trees rebalance on every insert.
Binary tree vs binary search tree?
A binary tree only limits each node to two children; a BST also keeps the left-smaller, right-bigger order.