Maximum Island Size in a Binary Tree

Moderate

0/80

0 upvote

Asked in company

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

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

7
1 1 0 0 1 -1 1

Sample Output 1:

Explanation for Sample 1:

There are two islands (subtrees of '1's) on this map:
  The node at the bottom right is an island of size 1.
  The root node (1), its left child (1), and that child's right child (1) form a connected group of three land blocks.
The largest size is 3.

Sample Input 2:

7
0 1 1 1 -1 1 1

Sample Output 2:

Explanation for Sample 2:

The root is a water block, so it breaks any connection between its children.
  The left subtree contains an island of size 2 (1 -> 1).
  The right subtree contains an island of size 3 (1 -> 1 -> 1).
The largest size is 3.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= N <= 10^5
Node values will be 0, 1, or -1 (for input representation only).

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Island Size in a Binary Tree

Console