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)
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →