binary search tree (BST)

A binary search tree (BST) is a binary tree that keeps its keys in sorted order, so that searching for, inserting, or deleting a value can discard half the remaining nodes at each step. Every node holds a key, and the tree maintains one invariant: all keys in a node’s left subtree are smaller than the node’s key, and all keys in its right subtree are larger.

That ordering turns a lookup into a walk down a single path. A search compares the target with the current node and moves left when the target is smaller or right when it is larger, halving the candidates at each move much like a binary search over a sorted array. Reading the keys with an in-order traversal returns them in sorted order. That traversal visits a node’s left subtree, then the node itself, then its right subtree.

Step through a search in the tree below to watch that single path take shape: each comparison rules out a whole subtree, roughly halving the keys still in play.

Interactive diagram — enable JavaScript to view.

The cost of every operation is proportional to the tree’s height. A balanced tree keeps its height near log n for n nodes, giving O(log n) time. A tree built by inserting already-sorted keys instead degrades into a single chain of height n, collapsing to O(n), no better than scanning a linked list.

Self-balancing variants such as the AVL tree and the red-black tree restructure themselves on each change to keep the height logarithmic. Because the keys stay ordered, a binary search tree also supports operations a hash table cannot, such as finding the next-largest key or listing every key within a range.

Recursion in Python

Tutorial

Thinking Recursively in Python

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

intermediate python

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated Aug. 6, 2026
Computer Science Glossary Share Feedback