DataTerminology.comNEW
Also known as: BST
A node-based data structure maintaining sorted keys with left descendants smaller and right descendants larger for efficient search, insert, and delete.
DESCRIPTION
A binary search tree organizes comparable keys to enable logarithmic-time search, insertion, and deletion in average cases. Its structure depends on insertion order; unbalanced trees degrade to linear performance. Balanced variants like AVL or Red-Black trees enforce constraints to maintain height. BSTs underpin symbol tables, ordered maps, and range queries. Augmentations enable order statistics and interval operations.
ALTERNATIVE DEFINITIONS
Wikipedia
A binary search tree (BST) is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key; The right subtree of a node contains only nodes with keys greater than the node’s key; The left and right subtree each must also be a binary search tree.
Lists canonical ordering properties and recursive structure requirements.
Princeton Algorithms
Binary search trees are a data structure that quickly supports search, insert, and delete of keys by maintaining a symmetric order among nodes.
Focuses on symmetric order and operations performance.
GeeksforGeeks
A Binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key; The right subtree of a node contains only nodes with keys greater than the node’s key; The left and right subtree must also be binary search trees.
Presents the standard definition with emphasis on properties.
RELATED TERMS
Balanced Binary Search Tree B-Tree Binary Tree Heap Hash Table Order Statistics Tree Trie Skip List
COMPETING TERMS
Red-Black Tree AVL Tree
KNOWLEDGE AREAS
Programming Languages Software Engineering Data Modeling
TARGET AUDIENCE
Software Developer Data Engineer Software Architect Full Stack Developer
EXTERNAL SOURCES
- Wikipedia - Binary search tree
- Princeton Algorithms - Textbook section on BSTs
- VisuAlgo - Interactive visualization of BST operations
TOP QUESTIONS
What makes a Binary Search Tree efficient?
Its ordering invariants allow logarithmic-time search, insert, and delete on average. Balanced height is critical for sustained performance.
Category: Requirements
When does a Binary Search Tree perform poorly?
If keys are inserted in sorted order without balancing, the tree becomes a linked list, yielding linear-time operations.
Category: Mistakes
What is a hot topic around Binary Search Trees?
Self-balancing variants like Red-Black and AVL maintain height guarantees for consistent performance in production systems.
Category: Topic
How is a Binary Search Tree typically implemented?
Using nodes with key, value, left and right pointers; methods maintain invariants during insert and delete operations.
Category: Example
What are alternatives to Binary Search Trees?
Balanced trees like AVL or Red-Black, or hash tables for average constant-time lookups without ordering.
Category: Alternatives
How do Binary Search Trees support range queries?
In-order traversal and subtree pruning enable efficient retrieval of keys within intervals.
Category: Example
What is the biggest misunderstanding about Binary Search Trees?
Assuming all BSTs guarantee logarithmic time; only balanced variants or randomness preserve height.
Category: Misunderstanding
How are Binary Search Trees used in practice?
They back ordered maps, symbol tables, and index structures in languages and databases.
Category: Example
How do Binary Search Trees compare to B-Trees?
B-Trees optimize disk access using multi-way nodes; BSTs are memory-focused with binary branching.
Category: Opinion