Google NG: Counting Islands in a Tree Structure (DFS Variant)

Google's New Grad coding rounds often reskin a classic to test transfer. This one is a classic islands variant—the grid swapped for a 0/1 tree structure. Based on an oavoservice student's Google NG debrief, this post shows how to transfer the "grid islands" DFS pattern cleanly onto a tree. At the end you'll find VO assist / VO proxy paths for anyone in a new-grad, career-switch, or backend job search.

1. Google NG Coding Round Overview

Google NG questions are mostly LeetCode Medium. For an adapted classic, ask "which prototype is this," then transfer the adjacency—far more efficient than reinventing from scratch.

2. Problem

A classic islands problem, slightly adapted: in a tree structure of 0s and 1s, an island is a group of connected 1s surrounded by 0s, or lying on the tree boundary. Write an algorithm to count how many islands the tree has.

3. Framing: transfer "grid islands" to "a tree"

The classic islands problem runs DFS/BFS on a grid, merging adjacent 1s into one blob and counting the blobs. Here the structure is a tree, but the core is identical: adjacency changes from "grid up/down/left/right" to "tree parent-child edges."

So: traverse all nodes; on a node that is 1 and unvisited, flood the whole connected component of 1s (only along parent-child edges where the neighbor is also 1), marking them visited, and increment the island count. 0 nodes naturally act as separators, splitting distinct 1 components.

Below the tree is an adjacency list, and val[u] is node u's 0/1 value:

def count_islands(adj, val, root):
    visited = set()
    islands = 0

    def dfs(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited and val[v] == 1:
                dfs(v)              # expand only along 1-1 edges

    # visit every node so each 1-component is counted exactly once
    for u in adj:
        if u not in visited and val[u] == 1:
            islands += 1
            dfs(u)
        else:
            visited.add(u)          # mark 0 nodes too, avoid rechecking
    return islands

#        1(1)
#       /    \
#     2(1)   3(0)
#     /        \
#   4(0)       5(1)
adj = {1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3]}
val = {1: 1, 2: 1, 3: 0, 4: 0, 5: 1}
print(count_islands(adj, val, 1))   # 2: {1,2} one island, {5} another

Time complexity: O(V + E) (each node and edge visited once; in a tree E = V−1, i.e. O(V)). Space complexity: O(V) (visited + recursion stack).

Tip: a deep tree can blow the recursion stack—mention "this can be rewritten as an iterative DFS with an explicit stack," and interviewers usually appreciate it.

4. On-the-Spot Reminders

• For an adapted classic, recognize the prototype first (here, grid islands), then transfer the adjacency.
• Nail the visited boundaries: mark 0 nodes? could deep recursion blow the stack?
• DFS expands only along "neighbor is also 1" edges; 0 nodes naturally separate components.
• State "the only difference from grid islands is adjacency" verbally before coding—it keeps the reasoning smooth.

FAQ

Q1: How do tree islands differ from grid islands?

The core algorithm is the same—DFS/BFS counting connected 1s. Only adjacency differs: grid is up/down/left/right, tree is parent-child edges. Swap the neighbor source and 0 nodes still act as separators.

Q2: Why mark 0 nodes during traversal too?

Adding 0 nodes to visited avoids the outer loop rechecking them; they belong to no island, so marking them keeps the logic clean without affecting the count.

Q3: What goes wrong with a very deep tree?

Recursive DFS can blow the stack on an extremely deep tree. Switch to an iterative DFS with an explicit stack, or cap recursion depth. Raising this proactively in the interview shows sensitivity to edge cases.

Q4: How do I prepare efficiently for Google NG coding rounds?

Drill by topic—graph and tree traversal, connected components / union-find, prefix sum / hashing, DP—timed and narrating your reasoning. For timed mocks by Google NG question type, line-by-line walkthroughs, or full VO assist / VO proxy support, see the path below.

Preparing for Google NG interviews?

Google NG coding rounds love classic-problem variants—what they reward is transfer and clear communication. oavoservice offers full Google prep: timed mocks on graph and tree traversal / connected components / prefix sum / DP high-frequency questions, framing and verbal-clarity polishing, and predictions by NG question type. Coaches include senior big-tech engineers, with full VO assist / VO proxy support.

Add WeChat Coding0201 now to get Google questions and coaching.

Contact

• WeChat: Coding0201
• Email: [email protected]
• Telegram: @OAVOProxy