Binary Search Tree

A binary search tree keeps values so that everything left of a node is smaller and everything right of it is bigger — so each comparison discards half of what is left.

An empty tree

In a binary search tree, everything in a node's left subtree is smaller and everything on the right is bigger.

Step 1 / 22
Nodes
0
Comparisons
0

Step by step

The example above, written out — the same steps the animation plays.

  1. 1An empty tree. In a binary search tree, everything in a node's left subtree is smaller and everything on the right is bigger.
  2. 2Insert 50. 50 becomes the root.
  3. 3Insert 30: compare with 50. 30 < 50: go left.
  4. 430 placed. The left spot under 50 is free: 30 goes there.
  5. 5Insert 70: compare with 50. 70 > 50: go right.
  6. 670 placed. The right spot under 50 is free: 70 goes there.
  7. 7Insert 20: compare with 50. 20 < 50: go left.
  8. 8Insert 20: compare with 30. 20 < 30: go left.
  9. 920 placed. The left spot under 30 is free: 20 goes there.
  10. 10Insert 40: compare with 50. 40 < 50: go left.
  11. 11Insert 40: compare with 30. 40 > 30: go right.
  12. 1240 placed. The right spot under 30 is free: 40 goes there.
  13. 13Insert 60: compare with 50. 60 > 50: go right.
  14. 14Insert 60: compare with 70. 60 < 70: go left.

…and 8 more steps — press Play above to watch them all.

What's happening?

  1. To insert, start at the root and go left for smaller, right for bigger, until there is a free spot.
  2. Searching follows the same path; each step rules out a whole subtree.
  3. 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.