Binary Search Tree vs Binary Tree
💡 Concept Name
Binary Tree vs Binary Search Tree (BST) – A binary tree is a general tree with up to two children per node, while a binary search tree follows a strict ordering: left < root < right.
📘 Quick Intro
A binary tree organizes data hierarchically but doesn't impose any ordering. A binary search tree adds the rule that left children must be smaller than the node, and right children must be larger, enabling efficient searches.
🧠 Analogy / Short Story
Imagine a bookshelf (binary tree) where books are placed randomly vs. a labeled library shelf (BST) where books are ordered by title—making it easy to find what you need.
🔧 Technical Explanation
- Binary Tree: Nodes have ≤ 2 children, no order.
- BST: Nodes also have ≤ 2 children, but left child < node < right child.
- Searching in BST is O(log n) in average case.
- Insertion and deletion preserve ordering in BST.
🎯 Purpose & Use Case
- ✅ Binary Tree: Tree traversals, expression parsing, generic hierarchy.
- ✅ BST: Fast lookup, insertion, deletion, and range queries.
💻 Real Code Example
// BST Node definition
public class Node {
public int Value;
public Node? Left, Right;
public Node(int value) { Value = value; }
}
// BST implementation
public class BST {
public Node? Root;
public void Insert(int value) {
Root = InsertRecursive(Root, value);
}
private Node InsertRecursive(Node? root, int value) {
if (root == null) return new Node(value);
if (value < root.Value)
root.Left = InsertRecursive(root.Left, value);
else if (value > root.Value)
root.Right = InsertRecursive(root.Right, value);
return root;
}
public void Delete(int value) {
Root = DeleteRecursive(Root, value);
}
private Node? DeleteRecursive(Node? root, int key) {
if (root == null) return null;
if (key < root.Value)
root.Left = DeleteRecursive(root.Left, key);
else if (key > root.Value)
root.Right = DeleteRecursive(root.Right, key);
else {
if (root.Left == null) return root.Right;
if (root.Right == null) return root.Left;
Node minNode = FindMin(root.Right);
root.Value = minNode.Value;
root.Right = DeleteRecursive(root.Right, minNode.Value);
}
return root;
}
private Node FindMin(Node root) {
while (root.Left != null)
root = root.Left;
return root;
}
}
❓ Interview Q&A
Q1: What is a binary search tree?
A: A binary tree where each node's left subtree contains values less than the node and the right subtree contains values greater than the node.
Q2: What are the key properties of a BST?
A: Left child < node < right child, no duplicate values, and ordered traversal.
Q3: How do you search for a value in a BST?
A: By comparing the target value to node values and moving left or right accordingly.
Q4: What is the average-case time complexity of BST operations?
A: O(log n) for search, insertion, and deletion.
Q5: What is the worst-case time complexity of BST operations?
A: O(n), which happens when the tree becomes skewed.
Q6: How do you insert a new value in a BST?
A: Recursively or iteratively find the correct leaf position and insert the node.
Q7: How is deletion handled in BSTs?
A: By three cases: deleting a leaf, deleting a node with one child, or deleting a node with two children.
Q8: What traversal methods are common in BSTs?
A: In-order, pre-order, and post-order traversals.
Q9: What is an in-order traversal in BST?
A: Traverses nodes in ascending order of values.
Q10: Why are BSTs useful?
A: They provide efficient dynamic data storage and quick search, insert, and delete operations.
📝 MCQs
Q1. What is a binary search tree?
- A tree with two children
- A tree where left < node < right
- A balanced tree
- A sorted list
Q2. What is the average-case search time in a BST?
- O(1)
- O(log n)
- O(n)
- O(n^2)
Q3. What causes the worst-case search time in BST?
- Balanced tree
- Skewed tree
- Complete tree
- Full tree
Q4. Which traversal of BST gives sorted order?
- Pre-order
- In-order
- Post-order
- Level-order
Q5. How many children can a BST node have?
- Only 2
- 0, 1 or 2
- Only 1
- Any number
Q6. What is the deletion case when node has two children?
- Delete directly
- Replace with in-order successor
- Replace with left child
- Replace with root
Q7. How do you insert into a BST?
- Always at root
- Find correct leaf position
- At the end of list
- Random place
Q8. Which traversal visits root first?
- In-order
- Post-order
- Pre-order
- Level-order
Q9. What property does BST maintain?
- Balanced nodes
- Ordered left and right subtrees
- Equal height
- Full binary tree
Q10. Why use a BST?
- Simple to implement
- Efficient search and dynamic updates
- Uses less memory
- Only for sorting
💡 Bonus Insight
To avoid unbalanced trees (which degrade BST to O(n)), use self-balancing trees like AVL or Red-Black Tree for large datasets.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!