Learn Number of Islands, Invert Binary Tree, and Course Schedule with Step-by-Step

Question

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? 👀👀

https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo

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

https://dev.to/nyaomaru/is-learning-dsa-boring-lets-use-dsa-view-view-two-sum-binary-search-and-bubble-sort-374o

https://dev.to/nyaomaru/learn-valid-parentheses-reverse-linked-list-and-tree-max-depth-with-step-by-step-visualization-in-3o09

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?

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.

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.

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.

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?

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. 😿

https://dsa-view-view.vercel.app/#s=j.eyJlIjoibnVtYmVyLW9mLWlzbGFuZHMiLCJsIjoidHlwZXNjcmlwdCIsIm0iOiJ2ZXJpZmljYXRpb24iLCJ2IjoxfQ

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.

🏝️😸

---

🌳 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?

😿

https://dsa-view-view.vercel.app/#s=j.eyJlIjoiaW52ZXJ0LWJpbmFyeS10cmVlIiwibCI6InR5cGVzY3JpcHQiLCJtIjoidmVyaWZpY2F0aW9uIiwidiI6MX0

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?

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.

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.

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?

https://dsa-view-view.vercel.app/#s=j.eyJlIjoiY291cnNlLXNjaGVkdWxlIiwibCI6InR5cGVzY3JpcHQiLCJtIjoidmVyaWZpY2F0aW9uIiwidiI6MX0

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.

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.

https://dsa-view-view.vercel.app

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? 😿

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 ⭐

https://github.com/nyaomaru/dsa-view-view

See you in the next article!