What is a Binar Search Tree?
A Binary Search Tree is a node-based binary tree data structure with the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key
- The right subtree of a node contains only nodes with keys greater than the node's key
- Both the left and right subtrees must also be binary search trees
- Each node contains a unique key (no duplicates)
Common Operations
Basic BST Operations
- Insert: Add a new node while maintaining BST properties
- Search: Find a node with a specific key value
- Delete: Remove a node and restructure the tree
- Traverse: Visit all nodes in a specific order (in-order, pre-order, post-order)
Time Complexity
Average case: O(log n) for search, insert, and delete operations
Worst case: O(n) when the tree becomes unbalanced (resembles a linked list)
Learn More
For a comprehensive guide on Binary Search Trees, visit: Wikipedia - Binary Search Tree