# Inorder Successor - Amazon Top Interview Questions

### Problem Statement :

Given a binary search tree root containing unique values, and an integer t, return the value of the inorder successor of t. That is, return the smallest value greater than t in the tree.

Note: you can assume that the inorder successor exists.

Bonus: solve it in \mathcal{O}(h)O(h) time and \mathcal{O}(1)O(1) space where h is the height of the tree.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [2, [0, null, [1, null, null]], [3, null, [4, null, null]]]
t = 2

Output

3

Example 2

Input

root = [2, [0, null, [1, null, null]], [3, null, [4, null, null]]]
t = 1

Output

2

### Solution :

                        Solution in C++ :

/**
* class Tree {
*     public:
*         int val;
*         Tree *left;
*         Tree *right;
* };
*/
int solve(Tree* root, int t) {
int ans = INT_MAX;
while (root != NULL) {
if (root->val > t) {
ans = min(ans, root->val);
root = root->left;
} else {
root = root->right;
}
}
return ans;
}


                        Solution in Python :

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def solve(self, root, t):

self.max_ele = float("inf")
self.traverse(root, t)
return self.max_ele

def traverse(self, root, t):
if not root:
return
if root.val <= t:
self.traverse(root.right, t)
else:
self.max_ele = min(self.max_ele, root.val)
self.traverse(root.left, t)


## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element