Binary Search Tree vs Binary Tree
💡 Concept Name
Binary Search Tree (BST) – A special type of binary tree where every node's left child is less than the node and every right child is greater. This structure powers fast searching and updates.
📘 Quick Intro
A binary tree allows each node up to two children but doesn't require any ordering. A BST is more than a binary tree—it enforces a sorted arrangement, making searches much faster, especially when balanced.
🧠 Analogy / Short Story
Imagine a basic family tree where parents can have two children in any order—that's a binary tree. A BST is like a library bookshelf sorted alphabetically: you know exactly where to find any book, and you never have to search blindly.
🔧 Technical Explanation
- 🌳 Binary Tree: Nodes may have up to two children; there’s no rule about values.
- 🔢 BST: For every node, all left descendants are less, all right descendants are greater—applies recursively.
- ⚡ Efficiency: In a balanced BST, search/insert/delete are O(log n); plain binary trees can degrade to O(n).
- 🔍 Use Cases: BSTs are best for situations where quick, ordered access or dynamic searching is required.
- ❗ Balance Matters: Without balancing, a BST can lose its speed advantage and become just a linked list.
🎯 Purpose & Use Case
- ✅ Use generic binary trees to model general hierarchies, e.g., parse trees or representing nested structures.
- ✅ Use BSTs to build dictionaries, sets, and indexes where fast search is crucial.
- ✅ Self-balancing BSTs (like AVL, Red-Black) are ideal for applications needing always-fast inserts, deletes, and lookups.
💻 Real Code Example
public class BSTNode
{
public int Value;
public BSTNode? Left;
public BSTNode? Right;
public BSTNode(int value) { Value = value; }
public void Insert(int newValue)
{
if (newValue < Value)
{
if (Left == null) Left = new BSTNode(newValue);
else Left.Insert(newValue);
}
else
{
if (Right == null) Right = new BSTNode(newValue);
else Right.Insert(newValue);
}
}
}
// Usage:
var root = new BSTNode(10);
root.Insert(5);
root.Insert(15);
❓ Interview Q&A
Q1: What is the key difference between a binary tree and a binary search tree?
A: A binary search tree maintains left < root < right order; a binary tree does not.
Q2: Is every BST a binary tree?
A: Yes—all BSTs are binary trees, but not all binary trees are BSTs.
Q3: Why are BSTs efficient for search?
A: The order allows for elimination of half the tree at each step, much like binary search.
Q4: What if a BST is unbalanced?
A: It can degrade to O(n) time, just like a linked list.
Q5: What traversal gives sorted order in BST?
A: In-order traversal.
Q6: Name two types of self-balancing BSTs.
A: AVL Tree and Red-Black Tree.
Q7: Can binary trees have duplicate values?
A: Yes; BSTs typically disallow or restrict duplicates for efficient search.
Q8: What is the time complexity for insert in a balanced BST?
A: O(log n).
Q9: Which application often uses BSTs under the hood?
A: Database indexing, in-memory sets, and sorted dictionaries.
Q10: Which operation can be slow on an unbalanced BST?
A: Search, insert, and delete can all become slow (O(n)).
📝 MCQs
Q1. What is the defining property of a BST?
- No property
- Balanced children
- Left < Root < Right
- No children
Q2. Which traversal gives sorted output in BST?
- Post-order
- Pre-order
- In-order
- Level-order
Q3. Can a BST have duplicate elements?
- Yes always
- Usually not
- Only even numbers
- Only integers
Q4. What is time complexity of insert in balanced BST?
- O(1)
- O(n)
- O(log n)
- O(n log n)
Q5. Which is NOT a self-balancing BST?
- AVL
- Red-Black
- Heap
- Splay
Q6. Which tree structure ensures no ordering among nodes?
- Binary Tree
- BST
- AVL
- Trie
Q7. When is a BST worst-case O(n)?
- When balanced
- Always
- When unbalanced
- With duplicates
Q8. Which operation is fastest in BST if balanced?
- Search
- Sort
- Traverse
- Rebalance
Q9. Which property is true for BST?
- Sorted by structure
- Sorted by key
- Sorted alphabetically
- Sorted by height
Q10. Which data structure is ideal for dictionary implementation?
- Queue
- BST
- Graph
- Array
💡 Bonus Insight
Binary search trees are fundamental to many fast data operations, but always be mindful of tree balance. Modern languages and libraries offer self-balancing trees (like C#'s SortedDictionary) to ensure the speed doesn't degrade as your dataset grows.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!