🧠 90 Days DSA Challenge – Day 8

🔥 Introduction:

Welcome back to Day 8 of my 90 Days DSA Challenge!
Today, I dove deep into the recursive world of binary trees, where every call is a path and every return is a revelation.

We explored three essential problems that form the foundation of binary tree operations:

1. Inorder Traversal

2. Postorder Traversal

3. Maximum Depth of a Binary Tree

Understanding these patterns is vital — not just for interviews but also for developing a strong intuition for tree-based problems. In this blog, I’ll break down each problem using:

• A clean and structured Java solution

• Step-by-step code walkthroughs

• Physical (visual) interpretations of recursion

---

📘 1. Inorder Traversal of Binary Tree (Left → Root → Right)

✅ Problem Statement:

Given the root of a binary tree, return the inorder traversal of its nodes' values.

💡 Concept:

Inorder traversal follows the Left → Root → Right pattern.
This is particularly useful for BSTs because it returns elements in ascending order.

🔍 Code:

class Solution {
    public void inorderhelp(TreeNode root,List out){
        if(root==null){
            return;
        }
        inorderhelp(root.left,out);
        out.add(root.val);
        inorderhelp(root.right,out);
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>out=new ArrayList<>();
        if(root == null){
            return out;
        }
        inorderhelp(root,out);
        return out;
    }
}

🧠 Step-by-Step Explanation:

1. Base Case: If the current node is null, we return.

2. Recursive Calls: First go left, then process the current node, then go right.

3. Add to List: The out list accumulates node values in inorder fashion.

📌 Physical Representation:

       1
        \
         2
        /
       3

Inorder: 1 → 3 → 2

---

📘 2. Postorder Traversal of Binary Tree (Left → Right → Root)

✅ Problem Statement:

Given the root of a binary tree, return the postorder traversal of its nodes' values.

💡 Concept:

Postorder traversal follows the Left → Right → Root pattern.
It’s useful for deleting the tree or calculating space after children are visited.

🔍 Code:

class Solution {
    public void postorderhelper(TreeNode root,List out){
        if(root==null){
            return;
        }
        postorderhelper(root.left,out);
        postorderhelper(root.right,out);
        out.add(root.val);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>out=new ArrayList<>();
        if(root==null){
            return out;
        }
        postorderhelper(root,out);
        return out;
    }
}

🧠 Step-by-Step Explanation:

1. Base Case: If the node is null, return.

2. Recursive Calls: First go to left child, then right child.

3. Visit Root: Add the node value after children are done.

📌 Physical Representation:

       1
        \
         2
        /
       3

Postorder: 3 → 2 → 1

---

📘 3. Maximum Depth of Binary Tree

✅ Problem Statement:

Given the root of a binary tree, return its maximum depth.
Maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

💡 Concept:

Use recursion to explore each subtree and track the current depth level.
Use a helper function that updates a global answer based on max depth seen.

🔍 Code:

class Solution {
    private int answer;
    public void maxdepthhelper(TreeNode root, int depth){
        if(root==null){
            return;
        }
        answer=Math.max(answer,depth);
        maxdepthhelper(root.left,depth + 1);
        maxdepthhelper(root.right,depth + 1);
    }
    public int maxDepth(TreeNode root) {
        answer=0;
        maxdepthhelper(root,1);
        return answer;
    }
}

🧠 Step-by-Step Explanation:

1. Start from the root with depth = 1.

2. Traverse both left and right subtrees while increasing depth.

3. Use Math.max to update the maximum depth reached.

📌 Physical Representation:

       3
      / \
     9  20
        / \
       15  7

Max Depth = 3

---

🔚 Wrap-Up

Today’s focus was on recursive understanding — how problems can be broken down into sub-problems. These three traversal techniques are foundational and open the door to advanced tree algorithms later in the challenge.

🎯 Conclusion:

Today’s challenge gave me an even deeper appreciation for the elegance of recursion in trees. By solving Inorder, Postorder, and Maximum Depth traversal problems, I strengthened my understanding of traversal orderings and recursive logic flow.

Each traversal has its unique character:

• Inorder: Left ➡ Node ➡ Right (used in BSTs)

• Postorder: Left ➡ Right ➡ Node (used in deletion/tree cleanup)

• Depth: Tracking the longest path from root to leaf

With the solid grasp I’ve built today, I feel more confident handling advanced binary tree problems ahead.
🌱 Recursion might feel abstract, but once you see it unfold step-by-step, it becomes your best ally.

Stay tuned for Day 9, where we’ll climb to new heights of data structure mastery!
Let’s keep growing. 💪