Welcome to Day 8 of your coding interview journey.

So far, you’ve covered:

• ✅ Day 1: HashMaps
• ✅ Day 2: Sliding Window
• ✅ Day 3: Arrays
• ✅ Day 4: Two Pointers
• ✅ Day 5: Interval Problems
• ✅ Day 6: Binary Search
• ✅ Day 7: Heaps

Today, we step into a core computer science topic:

👉 Trees (Binary Trees)

---

🧠 What is a Binary Tree?

A Binary Tree is a structure where:

• Each node has at most 2 children
  • Left child
  • Right child

---

Example Structure:

        3
       / \
      9  20
         / \
        15  7

---

🔑 Why Trees Matter in Interviews

Trees test:

• Recursion
• Traversal techniques
• Data structure understanding

---

🌳 Basic Tree Node in Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

💡 Problem 1 – Maximum Depth of Binary Tree

---

🧩 Problem

Given the root of a binary tree:

👉 Return its maximum depth

(The number of levels from root to the deepest leaf)

---

🧠 Approach – Recursion (DFS)

👉 The depth of a node is:

1 + max(left_depth, right_depth)

---

🛠️ Solution in Python

def max_depth(root):
    if not root:
        return 0

    left = max_depth(root.left)
    right = max_depth(root.right)

    return 1 + max(left, right)

---

✅ Example

For the tree:

        3
       / \
      9  20
         / \
        15  7

Output:

3

---

⚡ Complexity

• Time: O(n)
• Space: O(h) (height of tree)

---

🎯 Key Insight

👉 This is a classic Divide & Conquer (DFS) problem

---

💡 Problem 2 – Binary Tree Level Order Traversal

---

🧩 Problem

Return the level order traversal of a tree:

👉 Nodes level by level (left to right)

---

✅ Example Output

[[3], [9, 20], [15, 7]]

---

🧠 Approach – Breadth-First Search (BFS)

👉 Use a queue to process nodes level by level

---

🛠️ Solution in Python

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

---

⚡ Complexity

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

---

🎯 Key Insight

👉 BFS processes nodes level by level

This pattern is extremely common in tree problems.

---

⚠️ Common Mistakes

• ❌ Confusing DFS vs BFS
• ❌ Forgetting base case (if not root)
• ❌ Not handling empty trees
• ❌ Mismanaging queue size for levels

---

🧪 Practice Problems

To master trees, try:

1. Same Tree
2. Invert Binary Tree
3. Diameter of Binary Tree
4. Balanced Binary Tree
5. Lowest Common Ancestor

---

🎯 Key Takeaways

• Trees rely heavily on:
  • Recursion (DFS)
  • Queues (BFS)
• Learn to identify:
  • Depth problems → DFS
  • Level problems → BFS

---

🚀 Your Challenge (Day 8)

Solve this:

Invert a binary tree (swap left and right nodes).

---

📌 Final Thoughts

Trees are one of the most important topics in interviews.

Once you’re comfortable with:

• DFS
• BFS

You’ll be able to solve a huge range of problems.