Last Updated: 14 Oct, 2025

Maximum Island Size in a Binary Tree

Moderate
Asked in company
Google inc

Problem statement

You are given a map represented as a binary tree. Each node in the tree is a block of land or water. A node with a value of 1 represents a land block, and a node with a value of 0 represents a water block.


An "island" is defined as a connected group of land blocks. In this tree structure, this means an "island" is a subtree where every node has the value 1.


Your task is to find the size of the largest possible island on this map. The size is the total number of nodes in that island (subtree of '1's).


Input Format:
The first line contains a single integer N, the number of nodes in the level-order representation of the tree.

The second line contains N space-separated integers, representing the tree in level-order format. A value of -1 indicates a null node.


Output Format:
Print a single integer representing the number of nodes in the largest island. If there are no land blocks, the answer is 0.


Note:
The largest island might not include the root of the tree. You must check all possible subtrees. This problem has an optimal substructure and is well-suited for a recursive (DFS) post-order traversal approach.