Skip to content

Islands in a Tree

Level: L3-L4 Topics: Binary Trees, DFS, Connected Components, Tree Isomorphism

Problem Statement

You are given a binary tree where each node holds a value of either 0 or 1. An "island" is defined as a maximal connected group of nodes with value 1, where two nodes are connected if one is the parent or child of the other and both have value 1. Nodes with value 0 act as separators (like water in the classic grid-based islands problem), and boundary nodes (leaves or the root) with value 1 also form parts of islands.

Find the number of islands in the tree.

Background & Constraints

  • The tree is a standard binary tree (each node has at most two children).
  • Node values are either 0 or 1.
  • A single node with value 1 whose neighbors all have value 0 counts as one island.
  • The tree can have up to 10^5 nodes.

Examples

Example 1:

        1
       / \
      0   1
     / \   \
    1   1   0
   /
  1

Islands:
- Island 1: root node (value 1, separated from right child's island by nothing —
  wait, root(1) -> right child(1) are connected, so they form one island)
- Root(1) connects to right child(1): one island = {root, right-child}
- Left child is 0, so it breaks the connection.
- Left-child's children: left-left(1) and left-right(1) are both children of
  a 0-node, so they are NOT connected to each other.
- left-left(1) -> its child left-left-left(1): connected, one island = {left-left, left-left-left}
- left-right(1): standalone island

Answer: 3 islands

Example 2:

    1
   / \
  1   1

All nodes are 1 and connected through the root.
Answer: 1 island

Hints & Common Pitfalls

  • Think of the tree edges as connections. Two nodes with value 1 that share a parent-child edge are in the same island. A node with value 0 breaks the chain.
  • Simple DFS approach: Traverse the tree. When you encounter a node with value 1 whose parent has value 0 (or the node is the root), you've found the start of a new island. Count these "island roots."
  • Common mistake: Treating siblings as connected. Two siblings with value 1 are only in the same island if their parent also has value 1. If the parent is 0, they belong to separate islands.
  • For the follow-up questions, think carefully about what makes two subtrees "the same shape."

Follow-Up Questions

  1. Instead of counting islands, return the size of each distinct island (sorted).
  2. Return the number of distinct island shapes. Two islands have the same shape if their underlying tree structures are isomorphic — the same branching pattern, ignoring node values and positions in the original tree.
  3. For the isomorphism follow-up: does the order of children matter? (i.e., is a left-child-only subtree the same shape as a right-child-only subtree?) Discuss both interpretations.
  4. What is the time complexity of checking tree isomorphism? Can you do it efficiently using hashing or canonical forms?