New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Guess Price

Contributed by

Himanshu Airan

Easy

0/40

10 mins

63 %

41 upvotes

+1 more

Problem Statement

Your friends gifted you a lot of things on your birthday, and now it's your turn to give some return gifts to them. You went to a gift store and decided to buy some Binary Search Trees (BST).

There is no salesperson in the store. So you are supposed to guess the price of a given BST, which is the minimum value in its nodes.

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

Input Format:

The first line contains 'T', denoting the number of test cases.
For each Test :
    The first line contains an integer, 'N'.
    The second line contains an array 'A' of 'N' space-separated integers, with a positive integer representing a node and -1 representing a NULL value.

The input array 'A' denotes Level Order traversal of the BST.
(Note that 'N' is not the number of nodes in the BST,  only positive integers in 'A' denote nodes of BST).

Output Format:

For each test case, print one integer, denoting the price of a given BST, i.e., minimum node value in it.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= A[i] <= 10^6 or A[i] = -1,  i ∈ (1, N)
Note - The sum of 'N' over all test cases does not exceed 2 * 10^5.

Time Limit: 1 sec

Sample Input 1:

2
13
5 4 6 3 -1 -1 7 1 -1 -1 -1 -1 -1
7
9 -1 10 -1 11 -1 -1

Sample Output 1

1
9

Explanation for Sample Input 1:

For Case 1:

Given input looks like the tree drawn above. It can be seen that the minimum value in the tree is 1.

For Case 2:

    Given input looks like the tree drawn above. It can be seen that the minimum value in the tree is 9.

Sample Input 2:

2
7
20 8 22 -1 -1 -1 -1
15
40 9 50 4 12 -1 -1 -1 -1 10 14 -1 -1 -1 -1

Sample Output 2:

8
4

Autocomplete

Console