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

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.