Skip to content
Back to Data StructuresAll lessons

Data Structures

Binary Search Tree

Search or insert: O(log n) when the tree is balanced, because each step cuts the search in half. O(n) if the tree becomes a lopsided chain.

The idea, in plain English

A binary search tree is like the game '20 questions,' turned into a shape. Each value can have up to two values below it. These are called its children. The smaller child goes on the left. The bigger child goes on the right. To find a value, start at the top. Keep asking 'is it smaller or bigger?' Step left or right each time.

How it works

  1. 1Start at the top (the root).
  2. 2Smaller than the current node? Go left. Bigger? Go right.
  3. 3Keep going until you find the value or hit an empty spot.

When you'd use it

Use this when you need data kept in sorted order, plus fast lookups and inserts. Reading it left to right, called in-order, gives you everything sorted for free.

Common beginner mistakes

  • Don't assume it's always fast. A tree built from already-sorted data becomes a slow straight line.
  • Don't mix up the rule. Smaller always goes left. Bigger always goes right.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Sorted: 1 3 4 5 7 8 9
Root: 5

See it in motion

Watch it branchBinary search treeSearch or insert: O(log n) when the tree is balanced, because each step cuts the search in half. O(n) if the tree becomes a lopsided chain.

Empty tree. Insert values one at a time.

0
Nodes
0
Comparisons
1/22
Step
0.0s
Time
ComparingOn the pathPlaced / foundSettled

Not sure this is the right topic? See the learning paths → or where this leads →