Second Largest in Tree Level

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a binary tree where each node contains an integer value. Your task is to find the second largest unique value at each level of the tree.

You must return a list of these second-largest values, ordered from the root level to the deepest level.

Rules for determining the second largest value:

If a level has two or more unique node values (e.g., [5, 5, 3]), the second largest is the second highest distinct value (in this case, 3).

If a level has fewer than two unique node values (e.g., [10] or [20, 20, 20]), there is no second largest value. In such cases, you should use -1 as a placeholder for that level's result.

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 line containing the second-largest values for each level, separated by spaces.

Note:

This problem is best solved by traversing the tree level by level, which is a classic application of Breadth-First Search (BFS). For each level, you will need to collect all node values and then apply a method to find the largest and second-largest unique values among them.

Sample Input 1:

6
1 2 3 4 5 6

Sample Output 1:

-1 2 5

Explanation for Sample 1:

Level 0: Contains [1]. Has fewer than two unique nodes. Result: -1.
Level 1: Contains [2, 3]. Largest is 3, second largest is 2. Result: 2.
Level 2: Contains [4, 5, 6]. Largest is 6, second largest is 5. Result: 5.
Final list: [-1, 2, 5].

Sample Input 2:

6
10 20 20 -1 -1 5 30

Sample Output 2:

-1 -1 5

Explanation for Sample 2:

Level 0: Contains [10]. Fewer than two unique nodes. Result: -1.
Level 1: Contains [20, 20]. Only one unique value (20). Result: -1.
Level 2: Contains [5, 30]. Largest is 30, second largest is 5. Result: 5.
Final list: [-1, -1, 5].

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= N <= 10^5
-10^9 <= Node Value <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Second Largest in Tree Level

Console