Difference between BST and Heap

---

Main purposes of a BST (Binary Search Tree):

1. Fast search

   • Because of the BST property (left < parent < right), you can ignore half of the tree at each step while searching.
   • Average time complexity: O(log n)
   • Worst case (unbalanced tree): O(n)

---

2. Keeps elements sorted

   • In-order traversal always gives the elements in ascending order.
   • Useful when you need both fast search and sorted order.

---

3. Efficient insert and delete

   • Adding a new element or removing an element also uses the same BST property.
   • Average: O(log n)

---

4. Flexible structure for other operations

   • Find min/max (just go far left/right)
   • Range queries (all elements between A and B)
   • Successor/predecessor of a node

---

Analogy:

Think of BST like a well-organized library:

• Books smaller than a number go to the left shelf, bigger go to the right shelf.
• Looking for a book? You don’t check all shelves, just follow the rule → fast.
• Want all books in order? Walk left → parent → right → sorted sequence.

---

Key difference vs Heap

Feature	BST	Heap
Fast search of any value	✅ O(log n)	❌ O(n)
Always sorted via traversal	✅ Yes	❌ No
Access to min/max	O(log n) (min = leftmost, max = rightmost)	✅ Top element only
Balanced trees needed for guaranteed O(log n)	✅ AVL, Red-Black	❌ N/A

---

So : BST is mainly about fast search + keeping elements in sorted order, whereas heap is mainly about fast access to the max or min element.