Count Islands in Binary Trees

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:

      1
     / \
    1   0
   / \   \
  1   1   0

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.

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.

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.

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
    }

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