Mastering Binary Trees and Sudoku: A Journey Through Depth and Logic in 90 Days

Introduction:

Welcome to Day 9 of my 90 Days DSA Challenge! Today, I focused on refining recursive logic and enhancing validation techniques. I tackled two essential binary tree problems using recursion and revisited the classic Valid Sudoku problem. This helped sharpen my understanding of tree depth analysis, path computation, and multidimensional constraint checking.

---

🌳 Problem 1: Maximum Depth of Binary Tree (Bottom-Up Approach)

🔎 Problem Statement:

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

💡 Main Idea:

The idea is to determine the maximum depth by evaluating the longest path from root to any leaf node, using post-order recursion (i.e., process left and right before the current node).

✅ Step-by-Step Approach:

1. If the current node is null, return 0.

2. Recursively call the left and right subtree.

3. Get the depth from the left and right.

4. Take the maximum of both depths.

5. Add 1 to include the current node.

6. Return this value to the previous call.

📝 Code:

class Solution {
    public int maxdepthhelper(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = maxdepthhelper(node.left);
        int right = maxdepthhelper(node.right);
        return 1 + Math.max(left, right);
    }

    public int maxDepth(TreeNode root){
        return maxdepthhelper(root);
    }
}

🧠 Examples & Visuals:

Example 1:

    1
   / \
  2   3

Dry Run:

• maxDepth(1) → max( maxDepth(2), maxDepth(3) ) + 1

• maxDepth(2) = 1 (leaf), maxDepth(3) = 1 (leaf)

• Result = max(1,1)+1 = 2 ✅

Example 2:

    1
   /
  2
 /
3

Dry Run:

• maxDepth(1) → maxDepth(2) + 1

• maxDepth(2) → maxDepth(3) + 1

• maxDepth(3) = 1 (leaf)

• Result = 1+1+1 = 3 ✅

Example 3:

    1
   / \
  2   3
 /     \
4       5

Dry Run:

• Left path: 1 → 2 → 4 = depth 3

• Right path: 1 → 3 → 5 = depth 3

• max(3,3) = 3 ✅

---

🌲 Problem 2: Path Sum

📊 Problem Statement:

Given a binary tree and a target sum, determine if there exists a root-to-leaf path such that the sum of the node values equals the given sum.

💡 Main Idea:

Use pre-order traversal (root, left, right) to traverse paths while maintaining a running total of node values. Check if the total equals the target at each leaf.

✅ Step-by-Step Approach:

1. Start at the root.

2. Add the current node's value to the running sum.

3. If you reach a leaf node, check if the running sum equals the target.

4. If it does, return true.

5. Otherwise, continue to left and right children.

6. If any path returns true, the overall result is true.

📝 Code:

class Solution {
    public boolean preorderhelper(TreeNode node, int targetsum, int sum){
        if(node == null){
            return false;
        }
        sum += node.val;
        if(node.left == null && node.right == null){
            return sum == targetsum;
        }
        return preorderhelper(node.left, targetsum, sum) || preorderhelper(node.right, targetsum, sum);
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        return preorderhelper(root, targetSum, 0);
    }
}

🧠 Examples & Visuals:

Example 1:

  5
 / \
4   8
    / \
   13  4
        \
         1
Target = 22

Dry Run:

• Path 5→4 = 9 ❌

• Path 5→8→13 = 26 ❌

• Path 5→8→4→1 = 18 ❌

• No valid path found

• Result: false ❌

Example 2:

  5
 / \
4   8
/     \
11     4
/  \
7    2
Target = 22

Dry Run:

• Path 5→4→11→2 = 5+4+11+2 = 22 ✅

• Result: true ✅

Example 3:

  1
 / \
2   3
Target = 5

• Path 1→2 = 3 ❌

• Path 1→3 = 4 ❌

• No valid path

• Result: false ❌

---

🔄 Problem 3: Valid Sudoku (Revised)

📆 Problem Statement:

Validate whether a 9x9 Sudoku board is valid. Only the filled cells need to be checked, not whether it is solvable.

💡 Main Idea:

Track all values seen in each row, column, and box using separate matrices. If a duplicate is found in any, the board is invalid.

✅ Step-by-Step Approach:

1. Traverse the board cell-by-cell.

2. Skip empty cells (denoted by '.').

3. Convert character to index (0-8).

4. Calculate box index using 3 * (r / 3) + (c / 3).

5. Check if the value already exists in row, column, or box.

6. If found, return false. Else, mark as seen.

📝 Code:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] cols = new int[9][9];
        int[][] boxes = new int[9][9];

        for(int r = 0; r < 9; r++){
            for(int c = 0; c < 9; c++){
                if(board[r][c] == '.') continue;
                int val = board[r][c] - '1';
                int boxIdx = 3 * (r / 3) + (c / 3);

                if(rows[r][val] == 1 || cols[c][val] == 1 || boxes[boxIdx][val] == 1){
                    return false;
                }

                rows[r][val] = 1;
                cols[c][val] = 1;
                boxes[boxIdx][val] = 1;
            }
        }
        return true;
    }
}

🧠 Examples & Visuals:

Example 1 (Valid):

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Dry Run:

• Traverse each row, column, and 3x3 box.

• No duplicates found.

• Result: true ✅

Example 2 (Invalid due to row duplicate):

5 3 . | . 7 . | . . 5
...

• Two 5's in the first row.

• Result: false ❌

Example 3 (Invalid due to box duplicate):

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 5 | . . . | . 6 .   ← duplicate '5' in top-left box

• Duplicate detected in top-left 3x3 box

• Result: false ❌

🧩 Where I Got Stuck & How I Solved It

When I initially revisited the Valid Sudoku problem, I got stuck understanding how to uniquely identify each 3x3 box in the grid. I was using just the row and column index, which led to incorrect validations as I couldn't differentiate between boxes.

int val = board[3][3] - '1'; Let’s assume:

board[3][3] = '5' (a char, not an int)

'5' has an ASCII value of 53

'1' has an ASCII value of 49

So what happens:

java Copy Edit val = '5' - '1' = 53 - 49 = 4 🤔 So we stored 4 — how does that represent digit 5? Here’s the magic: in zero-based arrays, we often use index = digit - 1 to map the digit to its correct array index.

Actual Digit Character ASCII Index Used (val) 1 '1' 49 0 2 '2' 50 1 3 '3' 51 2 4 '4' 52 3 5 '5' 53 4 ← 💡 you are here! ... ... ... ... 9 '9' 57 8 👉 So:

val = 4 → represents digit 5

That’s why we store/check at rows[row][4] (for digit 5)

🧠 Think of val as: "the zero-based index for the digit stored as a character on the board"

So even though val = 4, it logically means digit 5, and you use it to index the array like this:

java Copy Edit rows[row][val] → rows[3][4] → means digit 5 used in row 3 cols[col][val] → cols[3][4] → means digit 5 used in column 3 boxes[box][val] → boxes[4][4] → means digit 5 used in box 4 ✅ Summary: Yes, val = 4

But that value is just the array index for digit 5

This is a very common and efficient trick to map characters '1'–'9' to index 0–8 in Sudoku and similar problems

🔍 Line in question:

x = 3 * (r / 3) + (c / 3);

This formula gives a unique box index (0–8) for each of the 9 sub-boxes in the 9×9 Sudoku grid.

---

🧠 Visualize the Sudoku grid like this (divided into boxes):

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

Each 3×3 block is numbered as above.

---

🧮 Box Index Formula Breakdown:

x = 3 * (r / 3) + (c / 3)

• r / 3 → tells you which row group (0, 1, or 2) the cell is in

• c / 3 → tells you which column group (0, 1, or 2) the cell is in

Multiplying the row group by 3 and adding the column group gives you a unique box number from 0 to 8

---

✅ Let's go through a few examples:

---

🔸 Example 1: Cell (0, 0)

r = 0, c = 0
boxidx = 3 * (0 / 3) + (0 / 3) = 3 * 0 + 0 = 0

→ Belongs to top-left box (Box 0)

---

🔸 Example 2: Cell (4, 5)

r = 4, c = 5
boxidx = 3 * (4 / 3) + (5 / 3) = 3 * 1 + 1 = 4

→ Belongs to center box (Box 4)

---

🔸 Example 3: Cell (8, 8)

r = 8, c = 8
boxidx = 3 * (8 / 3) + (8 / 3) = 3 * 2 + 2 = 8

→ Belongs to bottom-right box (Box 8)

---

🔸 Example 4: Cell (6, 2)

r = 6, c = 2
boxidx = 3 * (6 / 3) + (2 / 3) = 3 * 2 + 0 = 6

→ Belongs to bottom-left box (Box 6)

---

📦 How it works in code:

if (boxes[boxidx][val] == 1) {
    return false; // Digit already exists in this box
}
boxes[boxidx][val] = 1; // Mark digit as seen in this box

So you’re storing whether a digit has been seen before in the 3×3 box using this computed index.

---

🧠 Takeaway:

• You use boxidx to track digits inside a 3×3 box

• The formula efficiently flattens a 2D 3×3 grid into a 1D array of size 9

---

Conclusion:

Today’s session reinforced essential concepts like recursive depth analysis, path validation, and constraint-based grid logic. Working with trees through both bottom-up and top-down approaches helped me appreciate the versatility of recursion. Meanwhile, revisiting Sudoku strengthened my ability to manage 2D arrays and logical conditions.

Onward to Day 10 with greater confidence and curiosity! 💪🌟

---

#90DaysDSAChallenge #DSA #BinaryTrees #Recursion #Sudoku #Java #Algorithm #CodingChallenge #Learning