Binary Search Trees (BST)
📘 Data Structure and Algorithm
👁 180 views
📅 Nov 05, 2025
⏱ Estimated reading time: 2 min
Binary Search Trees (BST)
A Binary Search Tree (BST) is a special type of binary tree that maintains order among elements to enable fast searching, insertion, and deletion.
Properties of BST
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree contains only nodes with keys greater than the node’s key.
- Both left and right subtrees are also binary search trees.
// Example (C++ structure)
struct Node {
int data;
Node* left;
Node* right;
};
BST Operations
- Search: Start from the root, move left or right depending on the key.
- Insertion: Insert new node at the correct position following BST property.
- Deletion: Three cases:
- Node with no child – simply remove it.
- Node with one child – replace it with its child.
- Node with two children – replace it with its inorder successor or predecessor.
Time Complexity
| Operation | Best Case | Worst Case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Applications
- Used in databases for indexing.
- Used in search and sort operations.
- Used in sets and maps implementation.
Conclusion
BSTs provide efficient data lookup, insertion, and deletion when balanced properly. They are a fundamental part of many algorithms and data management systems.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials