# Cutting Binary Search Tree - Amazon Top Interview Questions

### Problem Statement :

Given a binary search tree root, an integer lo, and another an integer hi, remove all nodes that are not between [lo, hi] inclusive.

Constraints

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

Example 1

Input

root = [2, [1, [0, null, null], null], [4, [3, null, null], null]]
lo = 3
hi = 4

Output

[4, [3, null, null], null]

Example 2

Input

root = [5, [1, null, null], [9, [7, [6, null, null], [8, null, null]], [10, null, null]]]
lo = 7
hi = 10

Output

[9, [7, null, [8, null, null]], [10, null, null]]

### Solution :

Solution in C++ :

Tree* solve(Tree* root, int lo, int hi) {
if (!root) return nullptr;
if (root->val < lo) return solve(root->right, lo, hi);
if (root->val > hi) return solve(root->left, lo, hi);
root->left = solve(root->left, lo, hi);
root->right = solve(root->right, lo, hi);
return root;
}

Solution in Python :

class Solution:
def solve(self, root, lo, hi):

if root is None:
return None

if root.val >= lo and root.val <= hi:
root.left = self.solve(root.left, lo, hi)
root.right = self.solve(root.right, lo, hi)
return root

elif root.val < lo:
return self.solve(root.right, lo, hi)

else:
return self.solve(root.left, lo, hi)

## 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