Learn Number of Islands, Invert Binary Tree, and Course Schedule with Step-by-Step Visualization in DSA View View 👀👀

Hoi hoi!

I’m @nyaomaru, a frontend engineer who is surprised by how cold it is in the Netherlands even though it’s still summer. 😸 Have you used DSA View View already? 👀👀 Features a timeline to step backward mid-loop I Built a Tool to Visualize DSA.

Let’s Learn Together! (DSA View View 👀👀) DSA View View allows you to understand DSA by visualizing how your implementation actually runs. In the previous articles, we looked at problems like: Two Sum Binary Search Bubble Sort Valid Parentheses Reverse Linked List Maximum Depth of Binary Tree Visualizing execution logic changes mental models Is Learning DSA Boring?

Let's Use DSA View View 👀👀 (Two Sum, Binary Search, and Bubble Sort) Curated progression from stacks to recursion Learn Valid Parentheses, Reverse Linked List, and Tree Max Depth with Step-by-Step Visualization in DSA View View 👀👀 This time, let's try three more classic problems: Number of Islands Invert Binary Tree Course Schedule These three problems introduce some very useful ways of thinking: Explore connected things Transform a tree with recursion Resolve dependencies in the right order The implementations are not huge.

But the runtime can become surprisingly difficult to hold in our heads. So let's view what actually happens. 👀 Let's learn together! 😸 🏝️ Number of Islands Let's start with Number of Islands.

Suppose we have this grid: 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 means land. 🏝️ 0 means water. 🌊 Land connected vertically or horizontally belongs to the same island. So how many islands are there? So how many islands are there?

Let's look at the first group. 1 1 1 These cells are connected. So they form one island. On the right side 1 1 1 Those cells are also connected. So the answer is 2. Nice! 🏝️🏝️ But how do we make the code understand that several 1s belong to the same island?

Find One Land, Then Explore All Connected Land The basic idea is When we find a new 1, count one island and visit all land connected to it. When we find a new 1, count one island and visit all land connected to it.

Let's use this implementation. function numIslands(grid: string[][]): number { let islands = 0; const visit = (row: number, col: number): void => { if (row < 0 || col < 0) return; if (row >= grid.length || col >= grid[row].length) return; if (grid[row][col] !

== "1") return; grid[row][col] = "0"; visit(row + 1, col); visit(row - 1, col); visit(row, col + 1); visit(row, col - 1); }; for (let row = 0; row < grid.length; row++) { for (let col = 0; col < grid[row].length; col++) { if (grid[row][col] === "1") { islands++; visit(row, col); } } } return islands; } There are two important parts.

First, we scan the grid for (let row = 0; row < grid.length; row++) { for (let col = 0; col < grid[row].length; col++) { Then, when we find land if (grid[row][col] === "1") { islands++; visit(row, col); } We count a new island. But then visit() does something important. It removes all land connected to that island from future consideration.

Why Do We Change 1 to 0? Inside visit() we have grid[row][col] = "0"; At first, changing land into water looks a little strange. 😿 But here, 0 really means We already visited this land. We already visited this land. Let's follow a tiny example.

1 1 1 0 We start at the top-left. And we found land! So islands = 1 Then visit(0, 0); Inside visit(), we mark it as visited. 0 1 1 0 Then we visit the four directions down up right left Going down finds another 1.

0 1 1 0 ↑ So we visit it too. 0 1 0 0 Going right from the original cell also finds land. Visit it. 0 0 0 0 Now the whole connected island has disappeared from our search. When the outer loops continue, there is no 1 left in that island to count again.

That's the key idea. Count once, then mark the whole connected area as visited. Count once, then mark the whole connected area as visited. Why Four Recursive Calls? We use visit(row + 1, col); visit(row - 1, col); visit(row, col + 1); visit(row, col - 1); That means up ↑ left ← current → right ↓ down Each visited cell asks Is there more land next to me?

Is there more land next to me? And every newly discovered land cell asks the same question again. This continues until we reach: water outside the grid land we already visited Those cases stop the recursion. The Base Cases These lines protect us if (row < 0 || col < 0) return; if (row >= grid.length || col >= grid[row].length) return; if (grid[row][col] !

== "1") return; So, If we walk outside the grid, stop. If we reach water, stop. If we reach a cell we already changed to 0, stop. Otherwise, continue exploring. Let's Follow Two Islands Consider 1 1 0 0 0 1 0 1 1 The scan begins at the top-left.

1 1 0 ↑ 0 0 1 0 1 1 Found land. islands = 1 visit() removes everything connected to it. 0 0 0 0 0 1 0 1 1 The loops continue. Eventually we reach 0 0 0 0 0 1 ↑ 0 1 1 Another 1.

So islands = 2 And visit() explores that entire connected area. 0 0 0 0 0 0 0 0 0 Done! 2 islands 🎉 Complexity Every cell is processed at most a small number of times. If the grid has m rows and n columns Time: O(m × n) In the worst case, the recursive call stack may grow with the number of land cells.

Space: O(m × n) 👀 Let's View View It This is one of those algorithms where the final code is pretty small. But while reading it, there are a lot of things moving at once row col grid islands recursive calls And then suddenly we see grid[row][col] = "0"; Why did that cell disappear? Which recursive call are we inside? Which cells belong to the current island?

Where will the outer loop continue after recursion finishes? That is a lot to simulate mentally. 😿 When we view it step by step, the idea becomes much more visual.

Find land ↓ islands++ ↓ visit connected land ↓ mark it visited ↓ expand up / down / left / right ↓ return to scanning ↓ find next island Instead of thinking about recursion first, I like to think about it like this Find one island, paint the whole island away, then keep searching. Find one island, paint the whole island away, then keep searching. 🏝️😸 🌳 Invert Binary Tree Next, let's invert a binary tree.

Suppose we have 4 / \ 2 7 / \ / \ 1 3 6 9 We want to change 4 / \ 7 2 / \ / \ 9 6 3 1 Every left child becomes the right child. Every right child becomes the left child.

Simple, right? Well, the final implementation is also surprisingly small. function invertTree(root: TreeNode | null): TreeNode | null { if (root === null) return null; const left = invertTree(root.left); const right = invertTree(root.right); root.left = right; root.right = left; return root; } That's almost suspiciously short. 👀 Go Down First Let's use a smaller tree.

1 / \ 2 3 We start at node 1. But we don't swap immediately. First, const left = invertTree(root.left); So we go to node 2. Node 2 also tries to invert its left child.

But there is no child. So if (root === null) return null; returns null. The same thing happens on the right side of node 2. Now node 2 has left = null right = null So root.left = right; root.right = left; does not visibly change anything.

Node 2 returns. Then node 1 explores its right subtree. 3 Node 3 also has no children, so it returns after the same process. Only then do we come back to node 1.

Now left = 2 right = 3 And we do root.left = right; root.right = left; So 1 / \ 2 3 becomes 👇 1 / \ 3 2 Done! 🎉 The Important Part: The Swap Happens on the Way Back This is what makes the recursive solution interesting. The function first goes down. 1 ↓ 2 ↓ null Then it comes back.

Later it explores the other side. 1 ↓ 3 ↓ null And after both children have returned, the current node swaps them. So the flow is more like Go left ↓ Invert left subtree ↓ Go right ↓ Invert right subtree ↓ Swap the returned subtrees ↓ Return current node The tree transformation is built while recursion unwinds.

A Slightly Bigger Example Let's look at 4 / \ 2 7 / \ 1 3 We start at 4. invertTree(4) Then invertTree(2) Then invertTree(1) Node 1 returns. Then node 3 returns. Now node 2 has left = 1 right = 3 Swap them. 2 / \ 3 1 Then recursion returns to 4.

The right subtree rooted at 7 is also processed. Finally node 4 receives left = inverted subtree rooted at 2 right = inverted subtree rooted at 7 and swaps them. The final tree becomes 4 / \ 7 2 / \ 3 1 The interesting thing is that each node only needs to know about its own two children.

It doesn't need to understand the whole tree. Complexity We visit every node once. Time: O(n) The recursive call stack depends on the height of the tree.

Space: O(h) For a balanced tree O(log n) In the worst case O(n) 👀 Let's View View It This is exactly where recursion can become difficult to mentally simulate. The code says const left = invertTree(root.left); const right = invertTree(root.right); Then root.left = right; root.right = left; But my brain immediately starts asking: Which root are we talking about now? Did node 2 already swap? Are we still going down?

Or are we coming back up? What does left contain at this moment? 😿 When we step through the runtime, we can separate two different movements. The final code is short. But the actual runtime has a rhythm 🎵 Go down ↓ Return ↓ Swap ↓ Return ↓ Swap Once I can see that rhythm, the recursive solution feels much less magical.

🌳😸 🎓 Course Schedule Finally, let's look at Course Schedule. This one is a little more difficult. Suppose we have three courses 0 1 2 And the prerequisites are [1, 0] [2, 1] That means To take course 1, finish course 0 first.

To take course 2, finish course 1 first. So the dependency looks like 0 → 1 → 2 Can we finish all courses? Yes. We can take them in this order 0 → 1 → 2.

Easy. But what if the dependencies look like this? 0 → 1 ↑ ↓ └── 2 Now 0 needs 2 1 needs 0 2 needs 1 Everyone is waiting for someone else. We can never start. That is a cycle.

And if there is a cycle, we cannot finish all courses.

Build the Graph Here is the implementation: function canFinish(numCourses: number, prerequisites: number[][]): boolean { const graph: number[][] = Array.from({ length: numCourses }, () => []); const indegree: number[] = Array(numCourses).fill(0); for (const [course, prerequisite] of prerequisites) { graph[prerequisite].push(course); indegree[course]++; } const queue: number[] = []; for (let course = 0; course < numCourses; course++) { if (indegree[course] === 0) queue.push(course); } let completed = 0; for (let head = 0; head < queue.length; head++) { const course = queue[head]; completed++; for (const next of graph[course]) { indegree[next]--; if (indegree[next] === 0) queue.push(next); } } return completed === numCourses; } There are a few moving parts here. graph indegree queue completed This is exactly the kind of algorithm where every individual line makes sense. but the whole thing can still feel confusing.

😿 Let's break it down. What Is graph? For 0 → 1 → 2 we want to know After I finish this course, which courses become closer to being available? After I finish this course, which courses become closer to being available?

So graph[0] = [1] graph[1] = [2] graph[2] = [] That means Finish 0 ↓ course 1 is affected Finish 1 ↓ course 2 is affected We build that here graph[prerequisite].push(course); What Is indegree? indegree tells us how many prerequisites a course is still waiting for. For 0 → 1 → 2 we have course 0: 0 prerequisites course 1: 1 prerequisite course 2: 1 prerequisite So indegree = [0, 1, 1] Course 0 is special.

Because it does not need anything before it. So we can start there immediately. Start With Courses That Need Nothing We build the queue for (let course = 0; course < numCourses; course++) { if (indegree[course] === 0) queue.push(course); } For our example indegree = [0, 1, 1] Only course 0 has zero prerequisites. So queue = [0] This means Course 0 is currently available.

Course 0 is currently available. Finish Course 0 Take course = 0 Then completed++; So completed = 1 Now look at courses depending on 0. graph[0] = [1] Course 1 was waiting for one prerequisite. But course 0 is now complete. So indegree[1]--; Then indegree[1] = 0 Now course 1 needs nothing. So we add it to the queue. queue = [0, 1] Finish Course 1 Next course = 1 Now completed = 2 Course 2 depends on 1.

So indegree[2]: 1 → 0 Add it to the queue. queue = [0, 1, 2] Finish Course 2 Finally course = 2 So completed = 3 And numCourses = 3 Therefore completed === numCourses; // true We can finish everything! 🎉 Why Does This Detect a Cycle? Now let's try 0 → 1 ↑ ↓ └── 2 Every course has one prerequisite.

So indegree = [1, 1, 1] We try to build the initial queue. if (indegree[course] === 0) But there is no course with indegree 0. So, nothing can start. Therefore completed = 0 And, 0 === 3 // false We cannot finish the courses. Another Example Suppose 0 → 2 1 → 2 2 → 3 Course 2 needs both 0 and 1.

So indegree = [0, 0, 2, 1] The initial queue is queue = [0, 1] Finish 0. indegree[2]: 2 → 1 Course 2 is still waiting. So don't add it yet. Finish 1. indegree[2]: 1 → 0 Now course 2 is ready. queue = [0, 1, 2] Finish 2. indegree[3]: 1 → 0 Now queue = [0, 1, 2, 3] Everything can be completed. This is the key idea When all prerequisites for a course are resolved, that course becomes available.

When all prerequisites for a course are resolved, that course becomes available. Why Use head Instead of shift()? The queue is processed like this for (let head = 0; head < queue.length; head++) { const course = queue[head] Instead of repeatedly doing queue.shift(); we keep an index pointing to the next item to process. So the queue can grow while we iterate through it.

For example queue = [0] process 0 ↓ queue = [0, 1] process 1 ↓ queue = [0, 1, 2] head simply moves forward. 0 → 1 → 2 ↑ head Then 0 → 1 → 2 ↑ head Then 0 → 1 → 2 ↑ head Complexity V = number of courses E = number of prerequisite relationships We build the graph once and process every course and edge. Time: O(V + E) Space: O(V + E) 👀 Let's View View It This is probably the most interesting visualization of the three.

Because there are several things changing together. graph indegree queue head completed If I only read indegree[next]--; if (indegree[next] === 0) queue.push(next); I understand the syntax. But I may still ask: Why did this course become available now? Which prerequisite was removed? Why is this course still not in the queue?

What does completed tell us? Where exactly does the cycle get stuck? When we view the runtime, we can watch the dependencies disappear. 0 → 1 → 2 indegree = [0, 1, 1] queue = [0] ↓ finish 0 indegree = [0, 0, 1] queue = [0, 1] ↓ finish 1 indegree = [0, 0, 0] queue = [0, 1, 2] ↓ finish 2 completed = 3 The code stops feeling like mysterious bookkeeping.

We're really doing one simple thing: Keep taking courses that are ready, and make their dependent courses closer to being ready. Keep taking courses that are ready, and make their dependent courses closer to being ready. If eventually every course becomes ready completed === numCourses there is no blocking cycle.

If some courses never become ready completed < numCourses something is stuck in a cycle. 🎓😸 🧠 What Did We Actually Learn? These three problems look very different. But each one teaches a useful way of thinking.

Number of Islands When you find one part of a connected group, explore the entire group before continuing. What else is connected to this? Invert Binary Tree Let recursive calls solve the smaller subtrees first, then transform the current node using their results. Can my children finish their work before I change this node?

Course Schedule Process things that have no unresolved dependencies, then use them to unlock more work. What can I safely process right now? The implementations are not very long.

But each one introduces a different mental model. DFS on a grid Recursive tree transformation Topological sorting And once again, the syntax is not really the hardest part. The difficult part is keeping track of the changing state.

Where are we? What changed? What is waiting? What has already been visited? Which recursive call are we inside? Sometimes I can read every line and still lose the thread somewhere in the middle.

😿 That's exactly when I want to view it. 👀👀 🎯 Conclusion In this article, we looked at: Number of Islands with recursive grid traversal Invert Binary Tree with recursion Course Schedule with topological sorting And more importantly, we followed what changed while each algorithm was running. For Number of Islands, we watched connected land disappear as it became visited.

1 → 0 For Invert Binary Tree, we watched recursive calls go down and the tree change while they returned. go down ↓ come back ↓ swap For Course Schedule, we watched prerequisites disappear and new courses enter the queue. indegree-- ↓ 0 prerequisites ↓ queue.push() This is exactly the kind of thing I built DSA View View for.

You can write or load a TypeScript implementation, run it with your own inputs, and move backward and forward through the runtime. If you are learning DSA too, try viewing one of these problems step by step. Especially when the implementation looks short, but your brain still says Wait... what just changed?

😿 Wait... what just changed? 😿 Seeing the runtime may make the idea much easier to follow. And if there is a DSA problem you want me to cover next, please let me know in the comments! I still have many algorithms to learn myself.

😸 Let's train our DSA muscles together! 💪 If you like DSA View View, please give it a star ⭐ nyaomaru / dsa-view-view DSA View View allows you to understand DSA to see the data flow. 👀👀 Of course, it's free. DSA View View turns TypeScript algorithm functions into step-by-step visual stories.

👀👀 Write code, run it with structured inputs, and see the arrays, matrices trees, lists, stacks, pointers, and return values move as the function executes. It is built for those moments when reading the code is not enough and you want to view why the answer changes. Why Try It? 🧠 Step through real TypeScript Paste or edit a function, validate it, then run the exact code in the browser.

🧠 Step through real TypeScript Paste or edit a function, validate it, then run the exact code in the browser. 🧩 Views that match the data Arrays become bars, matrices become grids, trees become node graphs, linked lists become chains, and two-pointer area problems get their own visual view.

🧩 Views that match the data Arrays become bars, matrices become grids, trees become node graphs, linked lists become chains, and two-pointer area problems get their own visual view. 🌳 DSA-friendly inputs out of the box TreeNode, ListNode, MinHeap, MaxHeap, PriorityQueue, nested arrays matrices, strings, numbers, and class-style inputs are supported without ceremony.

🌳 DSA-friendly inputs out of the box TreeNode, ListNode, MinHeap, MaxHeap, PriorityQueue, nested arrays matrices, strings, numbers, and class-style inputs are supported without ceremony. 🔎 39 built-in examples Search by name, browse… 🔎 39 built-in examples Search by name, browse… See you in the next article!