Overview
A Binary Search Tree supports search, insertion, and deletion by comparing the target key at each node and descending left or right according to the ordering invariant.
FoundationSource checked
Binary Search Tree
Stores ordered keys in a tree where left descendants are smaller and right descendants are larger.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Search Tree
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 8
- Code example
- Ready
- Visualization
- Ready
- Aliases
- BST
Core Concepts
ordering invarianttree searchinorder traversalunbalanced height
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use it to teach ordered search trees and recursive tree operations.
- Use balanced variants when sorted traversal and logarithmic operations are needed.
- Use it when range-order behavior matters more than hash lookup.
When Not to Use
- Avoid an unbalanced BST for adversarial or sorted insertion orders.
- Avoid it when O(1) average lookup is more important than ordering.
- Avoid it when duplicate-key policy is not defined.
What It Does
- Maintains ordered tree structure
- Searches by comparing at each node
Use Cases
- Ordered sets
- Sorted maps
- Range queries
Inputs
- Comparable keys or values
Outputs
- Tree structure
- Lookup or traversal results
Pseudocode
- 1.Start at the root
- 2.Compare the target with the current node
- 3.Move left if the target is smaller
- 4.Move right if the target is larger
- 5.Stop when the target or an empty child is reached
Canonical Example
- Input
- operations = insert 5, insert 2, query 5
- Output
- query result = found
- Explanation
- Binary Search Tree: The structure stores data so later operations can answer efficiently.
Implementation Notes
- Define whether duplicates are rejected, counted, or placed consistently on one side.
- Use predecessor or successor replacement carefully during deletion.
- Prefer self-balancing trees for production ordered maps.
Common Pitfalls
- Assuming an ordinary BST stays balanced.
- Breaking the ordering invariant during deletion.
- Handling duplicate keys inconsistently.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow comparisons guiding a search down left and right branches.
Step 1 of 5: Start at the root
ordered-treeNotes
The basic BST is a foundation for balanced trees such as AVL and red-black trees.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Binary Search Tree.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsSplay Tree
Data Structures · Extended
Splay Tree is a data-structure variant of Binary Search Tree with different update or query tradeoffs.
Compare with thisHas variantsTreap
Data Structures · Extended
Treap is a data-structure variant of Binary Search Tree with different update or query tradeoffs.
Compare with thisAlternativesSkip List
Data Structures · Core
Skip lists provide ordered-map operations using layered lists instead of tree rotations.
Compare with thisUsed byBinary Space Partitioning Dungeon Generation
Procedural Generation · Extended
BSP dungeon generation recursively partitions space in a tree-like structure.
Compare with thisRelationships
View full relationship pageGeneralizesAVL Tree
AVL trees are self-balancing binary search trees.
GeneralizesRed-Black Tree
Red-Black Trees are balanced binary search tree variants.
Related Algorithms
Tags
Data StructureTreeSearch