vizlearn
Home / Algorithms

Binary Search Trees

Algorithms & Data StructuresBy Updated

Smaller on the left, larger on the right — one rule that turns search into a series of halvings. Then insert sorted data and watch the whole structure collapse into a linked list.

Controls

Traversal

The Tree

step 0

Insight

The BST rule, applied at every node: everything in the left subtree is smaller, everything in the right subtree is larger.

nodes0
height0
ideal height0
last search steps–

Complexity

Search (balanced) O(log n)
Search (degenerate) O(n)
Space O(n)

Overview

A binary search tree stores ordered values in nodes: smaller keys go left and larger keys go right. Search, insert, and delete follow one path, taking O(h) time for tree height h. A balanced tree has logarithmic height; an unbalanced one can become a linear chain.

Search, Insert, Delete

Searching is a walk: compare with the current node, go left if smaller, right if larger, stop when equal or when you fall off the tree. Insertion follows the same walk and attaches the new node where the search failed.

Deletion is the fiddly one, with three cases:

  • Leaf — just remove it.
  • One child — the child takes its place.
  • Two children — replace the value with its in-order successor (the smallest value in the right subtree), then delete that successor. Only this choice preserves the BST rule.

In-Order Traversal Sorts For Free

Visit left subtree, then the node, then the right subtree. Because of the BST rule, this emits every value in ascending sorted order — press In and read the output.

The other two orders have their own uses: pre-order (node first) is how you copy or serialise a tree, and post-order (node last) is how you delete one safely, since children are freed before their parent.

The Fatal Weakness

Press Sorted input. Inserting already-sorted values means every new value is larger than everything before it, so it always goes right. The tree becomes a single downward chain — a linked list wearing a tree costume.

Height goes from O(log n) to O(n), and every operation degrades with it. This is not a rare edge case: inserting sorted data is extremely common in practice.

Which Is Why Self-Balancing Trees Exist

AVL trees and red-black trees detect when a subtree grows lopsided and perform rotations to restore balance, guaranteeing O(log n) regardless of insertion order. Red-black trees are what back std::map in C++ and TreeMap in Java.

Compare the height readout after pressing Balanced versus Sorted input with the same values — the gap is exactly what balancing buys.

BST or Hash Table?

A hash table is faster for pure lookup — O(1) versus O(log n). But a BST keeps its data ordered, which a hash table cannot. Use a tree when you need sorted iteration, range queries ("all values between 20 and 50"), or nearest-neighbour lookups. Use a hash table when you only ever ask "is this exact key present?".

The degenerate case

Insert 1, 2, 3, 4, 5 into an empty BST in that order and every node becomes the right child of the last. The tree is a linked list, and every operation is O(n).

Sorted input produces the worst possible tree. That is not a rare pathological case — inserting records in id order, or in date order, is entirely normal.

Three responses:

Self-balancing trees. AVL and red-black trees rotate on insertion to keep the height O(log n) automatically. This is what production implementations use.

Randomised insertion order, if you control it. Expected height O(log n).

A different structure. A sorted array with binary search, or a skip list, or a B-tree for disk-based data.

TreeBalance ruleCharacter
AVLHeights differ by at most 1Strictly balanced; faster lookups
Red-blackColour rules bound the heightFewer rotations; faster insertion
B-treeMany keys per nodeDesigned for disk pages
TreapRandom prioritiesSimple, probabilistic balance

Red-black trees are what most standard libraries use for ordered maps — C++'s std::map, Java's TreeMap — because they balance insertion and lookup cost well.

Guided tour

  1. Insert a few values and watch each one walk down the tree, going left or right at every comparison.
  2. Search for something. The highlighted path shows roughly half the remaining tree being discarded at each step.

Sources and next steps

Run it in Python

Insert, search, in-order traversal and delete — including the two-child delete that everyone gets wrong. The last block inserts sorted keys to show the tree collapsing into a linked list.

bst.pyPython 3
Output
How the code works
  1. node.left = insert(node.left, key)Assigning the result back is what builds the tree. The recursive call returns either the existing subtree or a brand-new node, and this line does not need to know which.
  2. if key < node.key: ... else: rightOne comparison discards an entire subtree, exactly like binary search on an array — the tree is that algorithm made into a structure that can also be inserted into cheaply.
  3. inorder: left, self, rightVisiting in that order emits the keys in sorted order, for free and without sorting anything. Change the position of the append and you have pre-order or post-order instead.
  4. successor = node.right; while successor.left:Deleting a node with two children means finding the next key in sorted order — the leftmost node of the right subtree — copying it up, and deleting that instead. It is guaranteed to have at most one child, so the hard case reduces to an easy one.
  5. sorted input -> height 7A BST's O(log n) is a property of its shape, not its definition. Sorted input produces one long spine, and every operation degrades to O(n). Self-balancing trees exist entirely to prevent this.
Change one thing
  • Insert [50, 30, 70, ...] shuffled with random.shuffle and print the height each time. Random order gives O(log n) with high probability — that is the usual defence.
  • Delete a leaf, a one-child node and the root, and print the traversal after each. It stays sorted, which is the invariant to test against.
  • Add a count to each node instead of ignoring duplicate keys. That is how a BST becomes a multiset.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: press Search. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Inserting sorted keys into a plain BST produces:
  2. An in-order traversal of a BST emits the keys:
  3. Deleting a node with two children works by:





 Cheat sheet
Binary Search Trees
Insert, search and delete in a BST and watch it degenerate into a linked list when values arrive sorted — the case balance fixes.
ALGORITHMS · vizlearn.in/dsa/binary_search_trees.html
More in Algorithms
AlgorithmsHeaps and Priority QueuesAlgorithmsHeap SortAlgorithmsTrie (Prefix Tree)AlgorithmsUnion-Find (Disjoint Set)
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact