aloalgo.comBinary Search Trees
A Binary Search Tree (BST) is a binary tree with an ordering property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This property enables efficient searching, insertion, and deletion.The BST Property
The defining characteristic of a BST is:- Left subtree: All values are less than the node
- Right subtree: All values are greater than the node
- Both subtrees must also be valid BSTs
BST Node Structure
Core Operations
| Operation | Average | Worst | Description |
|---|---|---|---|
| Search | O(log n) | O(n) | Compare and go left or right until found |
| Insert | O(log n) | O(n) | Search for position, then add as leaf |
| Delete | O(log n) | O(n) | Find node, handle 0/1/2 children cases |
| Min/Max | O(log n) | O(n) | Go all the way left (min) or right (max) |
Search
Start at the root. If target equals current value, found. If target is smaller, go left. If larger, go right. Repeat until found or reach null.Insert
Search for where the value should be, then insert as a new leaf node.Delete
Deletion has three cases:- Leaf node: Simply remove it
- One child: Replace node with its child
- Two children: Replace with inorder successor (or predecessor), then delete that node
Inorder Traversal = Sorted Order
A key property of BSTs: inorder traversal visits nodes in sorted order. This is extremely useful for validation and many BST problems.Validate BST
To check if a tree is a valid BST, ensure each node's value falls within valid bounds (updated as you traverse).BST vs Hash Table
| Feature | BST | Hash Table |
|---|---|---|
| Search | O(log n) | O(1) average |
| Ordered iteration | Yes (inorder) | No |
| Min/Max | O(log n) | O(n) |
| Range queries | Efficient | Inefficient |
| Floor/Ceiling | O(log n) | O(n) |
Common Interview Tips
- Inorder traversal: Many BST problems can be solved by leveraging the sorted inorder property.
- Bounds checking: For validation problems, pass min/max bounds down the recursion.
- Predecessor/Successor: The inorder predecessor is the rightmost node in the left subtree; successor is leftmost in right subtree.
- LCA in BST: Unlike general trees, you can use the BST property to find LCA in O(h) without visiting all nodes.
- Watch for duplicates: Clarify how duplicates should be handled (often placed in right subtree).
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.