Last Updated: 13 Dec, 2021
Guess Price
Easy
Asked in companies
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.
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
Approaches
Approach: Maintain a variable to store the minimum value in the tree. Do any traversal of your choice (Inorder, Preorder, Postorder, etc.) on the tree, and for each node, update the variable to keep track of the minimum value.
Algorithm:
- Create a variable 'ans' to keep track of the minimum value in the BST.
- Implement a recursive function to traverse the tree.
- The function accepts only one parameter: Pointer to a node in the BST.
- If the current node value is smaller than 'ans', update 'ans'.
- Call recursion on left and right children of the current node (if children are not NULL).
- Implementation of main function.
- Initialize 'ans' with root node value.
- Call above recursive function on the root node.
- Return' ans'.
Approach: Binary search tree (BST) follows a property that for each node, its left child can only have a smaller value than the parent, and a right child can only have a greater value. Thus, we don't need to check a right child at any instance.
Start from the root and move in only the left direction. The leftmost leaf node in the tree is our answer.
If the tree is left-skewed, this optimized approach works exactly the same as the normal traversal, shown in Approach-1.
Algorithm:
- Pointer to the root node is given.
- While the current node is not a leaf node.
- Move the pointer to left child of current node.
- Return the current node's value, which is the leftmost leaf node of the tree.