🧠 Day 7: Exploring Trees, Strings & Revisiting Linked Lists!

Welcome back, tech enthusiasts! On Day 7 of the 90 Days DSA Challenge, I explored a mix of Binary Tree Traversals and a String pattern search problem, and revised two previously covered Linked List problems. This blend of problems gave me a chance to focus on tree recursion, queue-based traversal, and brute-force string matching logic.

Let’s dive into each problem with clear code walkthroughs, visual breakdowns, and dry-run explanations. As always, I’m sharing visuals and my approach to help you master these concepts too.

---

✅ Problems Solved:

1. Binary Tree Preorder Traversal (Recursive)

2. Binary Tree Level Order Traversal

3. Find the Index of the First Occurrence in a String

4. Revised: Delete Node in a Linked List & Remove Nth Node from End

✅ Problem 1: Binary Tree Preorder Traversal (Recursive)

🔍 Problem Statement:

Traverse a binary tree in preorder: Root → Left → Right.

💡 Approach:

We use a helper method that recursively:

1. Visits the root.

2. Traverses the left subtree.

3. Traverses the right subtree.

🧠 Code:

public void preorderhelper(TreeNode root, List out){
    if(root == null) return;
    out.add(root.val);
    preorderhelper(root.left, out);
    preorderhelper(root.right, out);
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    preorderhelper(root, out);
    return out;
}

🧱 Physical Representation:

     1
     / \
    2   3
   / \
  4   5

Traversal Order: 1 → 2 → 4 → 5 → 3

🧾 Dry Run:

• Call: preorder(1) → add(1)

• Call: preorder(2) → add(2)

• Call: preorder(4) → add(4)

• Backtrack → preorder(5) → add(5)

• Backtrack → preorder(3) → add(3)

---

✅ Problem 2: Find the Index of the First Occurrence in a String

🔍 Problem Statement:

Given haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it doesn’t exist.

💡 Approach:

We slide a window of size needle.length() over haystack and compare characters one by one.

🧠 Code:

public int strStr(String haystack, String needle) {
    if(haystack.length() < needle.length()) return -1;

    for(int i = 0; i < haystack.length(); i++) {
        int j = 0;
        while(j < needle.length() && (i + j) < haystack.length()) {
            if(needle.charAt(j) != haystack.charAt(i + j)) break;
            j++;
        }
        if(j == needle.length()) return i;
    }
    return -1;
}

🧱 Example:

haystack = "leetcode", needle = "code"

Check substrings:

• "leet" ❌

• "eetc" ❌

• "etco" ❌

• "tcod" ❌

• "code" ✅ → returns 4

---

✅ Problem 3: Binary Tree Level Order Traversal (BFS)

🔍 Problem Statement:

Return a list of node values level by level using Breadth-First Search.

💡 Approach:

1. Use a Queue to process nodes.

2. For each level:

   • Add all node values to a temporary list.

   • Push their children into the queue.

🧠 Code:

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if(root == null) return out;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while(!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for(int i = 0; i < size; i++) {
            TreeNode node = queue.remove();
            level.add(node.val);

            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        out.add(level);
    }
    return out;
}

🧱 Physical Representation:

        1
       / \
      2   3
     /   / \
    4   5   6

Level Order Output:

[[1], [2, 3], [4, 5, 6]]

---

🔁 Revised Problems

Today, I also revisited two important Linked List problems to solidify my learning. You can read my in-depth article for these below:

• 🔗 https://my-dsa-grind-day-3-solutions.hashnode.dev/my-dsa-grind-day-5-solutions

---

🔚 Conclusion

Day 7 brought a perfect mix of string pattern recognition and tree traversal. The recursive depth of Preorder, the breadth-first magic of Level Order, and the precise logic behind String Matching made today’s problems really rewarding.

🧠 Lesson of the Day: A strong foundation in recursion and queue-based logic helps you tackle almost every tree-related problem in DSA!

---

📘 Want to follow my 90-day journey? Stay tuned every day for visual explanations, dry runs, and smart hacks to master DSA.

---

🔖 Tags:

#DSA #90DaysChallenge #BinaryTrees #StringProblems #Java #CodingInterview #DailyDSA #LinkedList #Recursion #BFS #TechBlogger #CTOBhaiya