Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Count Islands in Binary Trees

Given a binary tree where nodes have values (typically 0 or 1), analyze the 'islands' (connected components of similar values) within the tree. Tasks include counting the total number of islands, identifying unique island types based on their structure and size, and analyzing different patterns of island formations. An island is defined as a connected group of nodes with the same value.

Asked at:

Google

DESCRIPTION

Given a binary tree where each node contains a value, analyze the 'islands'—maximal connected components of nodes that share the same value. Your task is to count how many such islands exist, how large they are, and how different value-based regions form across the tree. Islands are determined strictly by parent–child connectivity.

Input:

nodes = [1, 1, 0, 1, 1, null, 0]

Output:

2 islands total: 1 island of value 1, 1 island of value 0

Explanation: Tree structure:

All 1s are connected through parent–child links, forming a single island of value 1 (size 4). The two 0s are connected to each other and form a single island of value 0 (size 2). Therefore, the tree has 2 islands total.

Constraints:

The number of nodes in the tree is in the range [0, 10^4]
Node values are typically 0 or 1, but can be any integer
An island is a maximal connected component of nodes with the same value
Two nodes are connected if they have a parent–child relationship

Understanding the Problem

Let's understand what we're being asked to do. We have a binary tree where each node contains a value (commonly 0 or 1), and we want to identify 'islands' — connected components of nodes with the same value.

Two nodes belong to the same island if and only if:

They have the same value, and
They are connected through parent–child links.

For example, consider the tree represented in level-order as [1, 1, 0, 1, 1, null, 0]. That corresponds to:

Here, all four 1 nodes are connected, forming one island. The two 0 nodes are connected to each other, forming one island. So this tree has 2 total islands.

Important constraint: Islands are based strictly on direct tree connectivity. Two nodes with the same value but located in different subtrees with no path consisting only of that value belong to different islands.

Edge cases to keep in mind:

Empty tree → 0 islands.
All nodes the same value → 1 island.
Every node differs from its parent → each node is its own island.
A single-node tree → exactly 1 island.

Building Intuition

When we move from a parent to a child, we need to check if the child's value matches the parent's value. If it matches, they belong to the same island. If it doesn't match, the child starts a new island.

This means we can count islands by counting how many times we encounter a 'boundary' - a transition from one value to a different value as we traverse parent-child connections.

By recognizing that islands are defined by connected components in the tree, we can use tree traversal to explore all nodes while tracking when we cross island boundaries.

Each time we see a value change from parent to child, we've discovered a new island. This transforms the problem from 'find all groups' into 'count value transitions' during traversal.

Think about coloring a map where adjacent regions must have different colors. In our tree, imagine painting each node - if a child has the same value as its parent, use the same paint color (same island). If different, grab a new paint color (new island).

As you traverse the tree, you're essentially counting how many different 'paint colors' you need. Each time you need a new color, you've found a new island. The tree structure naturally guides you through all the connections.

Common Mistakes

Forgetting to handle the root node as the start of an island - the root always begins a new island since it has no parent to compare with

Not tracking islands by their value - the problem asks for unique island types, not just total count, so we need to group by value

Confusing 'connected' with 'same value' - two nodes with the same value but in disconnected subtrees are NOT the same island

Incorrect base cases in recursion - forgetting to handle null nodes or leaf nodes properly can lead to incorrect counts or runtime errors

Not considering that island size matters for some variants - some problems ask for largest island, smallest island, or islands of specific sizes

Optimal Solution

Use depth-first search (DFS) to traverse the entire tree. As we visit each node, compare its value with its parent's value. If the values differ, we've crossed an island boundary and increment our island count. Track islands by their value to identify unique island types. This approach visits each node exactly once and makes one comparison per parent-child edge, efficiently counting all islands in a single traversal.

Visualization

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def count_tree_islands(root):
    """
    Count islands in a binary tree using DFS.
    An island is a connected group of nodes with the same value.
    """
    if not root:
        return {"total_islands": 0, "islands_by_value": {}}
    
    # Track total islands and islands grouped by value
    island_count = 0
    islands_by_value = {}
    
    def dfs(node, parent_val):
        nonlocal island_count
        
        if not node:
            return
        
        # If current node value differs from parent, new island starts
        if node.val != parent_val:
            island_count += 1
            
            # Track island by its value
            if node.val not in islands_by_value:
                islands_by_value[node.val] = []
            islands_by_value[node.val].append(island_count)
        
        # Continue DFS with current node's value as parent value
        dfs(node.left, node.val)
        dfs(node.right, node.val)
    
    # Start DFS - root is always the first island
    island_count = 1
    if root.val not in islands_by_value:
        islands_by_value[root.val] = []
    islands_by_value[root.val].append(island_count)
    
    # Traverse children
    dfs(root.left, root.val)
    dfs(root.right, root.val)
    
    return {
        "total_islands": island_count,
        "islands_by_value": islands_by_value
    }

Start counting islands in binary tree

0 / 29

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each of the n nodes in the tree exactly once during the DFS traversal, performing constant-time operations at each node

Space Complexity: O(h) The recursion stack uses O(h) space where h is the height of the tree. In the worst case (skewed tree), h = n, but for balanced trees h = log(n)

What We've Learned

DFS/BFS for connected components in trees: When counting islands or connected regions in a tree, use depth-first search (DFS) or breadth-first search (BFS) starting from each unvisited node with a target value - trees are naturally suited for traversal-based component detection since they lack cycles and have clear parent-child relationships.
Visited set with tree traversal: Unlike grid-based island problems, tree islands require tracking visited nodes using a HashSet during traversal because you may need to explore nodes through different parent-child relationships - mark nodes as visited when entering an island to avoid counting the same component multiple times.
Recursive island marking pattern: When you encounter an unvisited node with value 1 (or target value), increment your island counter and recursively mark all connected neighbors with the same value as visited - this flood-fill approach ensures each connected component is counted exactly once.
Tree traversal edge case: The most common mistake is forgetting to handle null nodes and single-node trees - always check if a node is null before accessing its value or children, and remember that a single node with value 1 constitutes an island of size 1.
Island structure characterization: Beyond counting, you can characterize islands by their subtree structure and size - use a serialization technique (like preorder traversal with null markers) to create unique signatures for island shapes, enabling detection of structurally identical islands across the tree.
Linear time complexity insight: This solution runs in O(n) time and O(h) space where n is the number of nodes and h is tree height - each node is visited exactly once during the initial traversal, and the recursion stack depth is bounded by tree height, making it optimal for tree-based connected component problems.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early December, 2025

Google

Mid-level

Late October, 2025

Google

Mid-level

Mid March, 2025

Google

Mid-level

Get Premium to View All 9 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Count Islands in Binary Trees

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact