Welcome to Day 9 of your coding interview journey.

Yesterday, we introduced Binary Trees.
Today, we take it one step further into a specialized and very important structure:

👉 Binary Search Trees (BSTs)

---

🧠 What is a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree with a special property:

👉 For every node:

• All values in the left subtree are smaller
• All values in the right subtree are larger

---

Example:

        5
       / \
      3   7
     / \   \
    2   4   8

---

🔑 Why BSTs Matter

BSTs allow efficient operations:

• Search → O(log n)
• Insert → O(log n)
• Delete → O(log n)

👉 (In balanced cases)

---

⚠️ Important Note

BST problems often test:

• Tree traversal
• Recursion
• Understanding constraints (not just structure!)

---

💡 Problem 1 – Validate Binary Search Tree

---

🧩 Problem

Given the root of a binary tree:

👉 Determine if it is a valid BST

---

❌ Common Mistake

Many people only compare:

node.left < node < node.right

❌ This is NOT enough!

---

🧠 Key Insight

Each node must respect a range:

• Left subtree → (min, node.val)
• Right subtree → (node.val, max)

---

🛠️ Solution in Python

def is_valid_bst(root):
    def helper(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return (
            helper(node.left, low, node.val) and
            helper(node.right, node.val, high)
        )

    return helper(root, float("-inf"), float("inf"))

---

⚡ Complexity

• Time: O(n)
• Space: O(h)

---

🎯 Key Insight

👉 Always think in ranges, not just parent-child comparisons

---

💡 Problem 2 – Lowest Common Ancestor (LCA) in BST

---

🧩 Problem

Given a BST and two nodes p and q:

👉 Find their lowest common ancestor

(The lowest node that has both as descendants)

---

Example:

        6
       / \
      2   8
     / \ 
    0   4
       / \
      3   5

👉 LCA of 2 and 8 → 6
👉 LCA of 3 and 5 → 4

---

🧠 Key Insight (BST Advantage)

Because it’s a BST:

• If both values are smaller → go left
• If both are larger → go right
• Otherwise → current node is the LCA

---

🛠️ Solution in Python

def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

---

⚡ Complexity

• Time: O(h)
• Space: O(1) (iterative)

---

🎯 Why This Works

👉 BST property lets us skip entire subtrees

This is much faster than general binary tree solutions.

---

⚠️ Common Mistakes

• ❌ Ignoring BST properties
• ❌ Using generic tree logic (slower)
• ❌ Forgetting edge cases (same node, root as LCA)
• ❌ Not validating full subtree ranges

---

🧪 Practice Problems

To master BSTs, try:

1. Insert into BST
2. Delete node in BST
3. Kth smallest element in BST
4. Convert sorted array to BST
5. BST iterator

---

🎯 Key Takeaways

• BSTs = ordered trees
• Always leverage:
  • Left < Node < Right
• Think in:
  • Ranges (validation)
  • Direction (search & LCA)

---

🚀 Your Challenge (Day 9)

Solve this:

Find the Kth smallest element in a BST.

(Hint: in-order traversal 😉)

---

📌 Final Thoughts

BSTs are extremely common in interviews because they combine:

• Trees
• Searching
• Optimization

Mastering them puts you ahead of many candidates.