Skip to content
BENIBIX Learn

Binary Search Tree (BST)

Development🧮 Algorithms & Data StructuresData Structures

Also known as BST, Binary Search Trees, Ordered Binary Tree

A binary tree kept in order. Small values go left; big ones go right.

Think of it like

Think of it like a guessing game. Too high, go left; too low, go right.

Example

Emma stores 1,000,000 scores in a balanced search tree. Finding one score takes about 20 steps instead of a million.

Why it matters

It gives fast search and keeps items sorted at the same time. Many database indexes use a close cousin of it.

Definition

A binary search tree is a binary tree that keeps its values in order. Everything in a node's left branch is smaller than it, and everything in its right branch is bigger. To find a value, you start at the root and go left or right at each step. If the tree stays balanced, that takes about 20 steps for a million values. If it grows lopsided, it can become as slow as a list.

Common mistake

Adding values that are already sorted to a plain search tree. It grows into one long line, and every search becomes slow.

Key takeaways

  1. 1
    Left is smaller. Right is bigger.
  2. 2
    Fast search. When it stays balanced.
  3. 3
    Keeps order. Read it left to right.

Compare