Practice/Google/Count Islands in Binary Trees

Count Islands in Binary Trees

CodingMust

Problem

You are given the root of a binary tree where each node contains an integer value (typically 0 or 1). Your task is to count the number of islands in the tree.

An island is defined as a maximal connected group of nodes that all share the same value. Two nodes are considered connected if they have a parent-child relationship in the tree. This means a node is connected to its parent (if it exists), its left child (if it exists), and its right child (if it exists).

Each island should be counted exactly once, and nodes with different values cannot be part of the same island even if they are adjacent in the tree structure.

Requirements

1. Implement a function that takes the root of a binary tree and returns the total count of islands
2. Each island must consist of nodes with identical values
3. Nodes are connected only through direct parent-child relationships (not sibling relationships)
4. Handle edge cases including empty trees and single-node trees
5. Each node should belong to exactly one island

Constraints

• The number of nodes in the tree is in the range [0, 1000]
• Node values are integers, typically 0 or 1, but can be any integer
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (due to recursion stack)

Examples

Example 1:

` Input: 1 /
0 1 /
0 0

Output: 3 Explanation: Three distinct islands exist:

• Island 1: Nodes with value 1 (root and root.right)
• Island 2: Node with value 0 (root.left by itself)
• Island 3: Nodes with value 0 (root.left.left and root.left.right) Note that root.left is not connected to its children's island because they are separated by root.left having value 0. `

Example 2:

` Input: 1 /
1 1 /
1 1

Output: 1 Explanation: All nodes have the same value and are all connected through parent-child relationships, forming one large island. `

Example 3:

` Input: 1 /
0 1 / / 1 0

Output: 5 Explanation: No two adjacent nodes share the same value, so each node forms its own island. `