Overview
A BK-tree stores each item as a node whose outgoing edges are labeled by metric distance. During approximate lookup, the triangle inequality prunes child distances that cannot fall within the requested tolerance.
CoreSource checked
BK-Tree
Indexes metric-space items by storing children at discrete distances from each node.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Metric Trees
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
approximate lookupmetric treesbranch and bounddata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when the distance function is a metric and query tolerances are small.
- Use when approximate lookup is needed over strings or other discrete objects.
When Not to Use
- Avoid when the distance function does not satisfy the triangle inequality.
- Avoid when high tolerances cause most branches to be searched anyway.
What It Does
- Stores items using metric distances from parent nodes
- Branches by integer distance values
- Prunes approximate queries with triangle-inequality bounds
Use Cases
- Fuzzy dictionary lookup
- Edit-distance spell checking
- Approximate matching in discrete metric spaces
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Insert the first item as the root
- 2.For each new item, compute distance to the current node
- 3.Follow or create the child edge labeled by that distance
- 4.For query, compute distance d to the current node
- 5.Search only child edges with labels between d - tolerance and d + tolerance
Canonical Example
- Input
- query 'book' with tolerance 1 in a tree containing 'books' and 'back'
- Output
- 'books' is returned; 'back' is pruned or rejected by distance
- Explanation
- Only branches whose edge distances can fall within the tolerance need to be searched.
Implementation Notes
- Keep the distance function deterministic and symmetric.
- For query distance d and tolerance t, inspect child distances in [d - t, d + t].
- Test exact matches, one-edit matches, and no-match queries.
Common Pitfalls
- Using a nonmetric distance invalidates the pruning rule.
- Large tolerance values can make queries approach a full traversal.
- Insertion order can affect tree shape and query cost.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow indexing metric-space items by discrete edit-distance branches on a small approximate lookup example.
Step 1 of 5: Insert the first item as the root
data-structures-mechanismNotes
BK-trees are most useful for discrete metrics such as Levenshtein distance with small edit tolerances.
Sources (1)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for BK-Tree metric-tree indexing and distance-based lookup.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toCover Tree
Data Structures · Extended
BK-trees and cover trees are alternative metric indexing structures with different branching rules.
Compare with thisUsed byBK-Tree Search
Pattern Matching · Core
BK-tree search traverses the metric index and prunes candidates using distance bounds.
Compare with thisRelationships
View full relationship pageUsed byBK-Tree Search
BK-tree search traverses the metric index and prunes candidates using distance bounds.
Alternative toCover Tree
BK-trees and cover trees are alternative metric indexing structures with different branching rules.
Conceptual neighborTrie
Both can support dictionary-like lookup, but BK-trees organize items by metric distance.
Related Algorithms
Tags
Data StructureApproximation