Given a Binary Search Tree (BST) and a range [min, max], remove all keys which are outside the given range. The modified tree should also be BST.
Example 1:
Input:
Range = [-10, 13]
Output:
-8 6 7 13
Explanation:
Nodes with values -13, 14 and 15 are 
outside the given range and hence are 
removed from the BST.
This is the resultant BST and it's 
inorder traversal is -8 6 7 13.
Example 2:
Input:
Range = [2, 6]
        14
      /    \
     4      16
    / \     /
   2   8   15
  / \  / \
 -8  3 7  10
Output:
2 3 4
Explanation:
After removing nodes outside the range, 
the resultant BST looks like:
               4
              /
             2
              \
                3 
The inorder traversal of this tree is: 2 3 4
Your task:
You don't have to read input or print anything. Your task is to complete the function removekeys() which takes the root node of the BST and the range as input and returns the root of the modified BST after removing the nodes outside the given range.
 
Expected Time Complexity: O(number of nodes)
Expected Auxiliary Space: O(h)
 
Constraints:
1 ≤ Number of Nodes ≤ 10^{5}
1 ≤ K ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        

'''



class Solution:

    def removekeys(self, root, l, r):

        #code here

Solutions:
class Solution:

	def removekeys(self, root, l, r):
		if root is None:
			return root
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data > r:
			return root.left
		if root.data < l:
			return root.right
		return root


class Solution:

	def removekeys(self, root, l, r):
		if root != None:
			if root.data < l:
				root = self.removekeys(root.right, l, r)
			elif root.data > r:
				root = self.removekeys(root.left, l, r)
			else:
				left = self.removekeys(root.left, l, r)
				right = self.removekeys(root.right, l, r)
				root.left = left
				root.right = right
			return root


class Solution:

	def removekeys(self, root, l, r):

		def rec(root):
			if not root:
				return
			root.left = rec(root.left)
			root.right = rec(root.right)
			if root.data < l:
				return root.right
			if root.data > r:
				return root.left
			return root
		return rec(root)


class Solution:

	def removekeys(self, root, l, r):
		if not root:
			return None
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l:
			rght = root.right
			return rght
		if root.data > r:
			lft = root.left
			return lft
		return root


class Solution:

	def removekeys(self, root, l, r):

		def helper(root):
			if not root:
				return None
			root.left = helper(root.left)
			root.right = helper(root.right)
			if root.data < l:
				return root.right
			if root.data > r:
				return root.left
			return root
		return helper(root)


class Solution:

	def removekeys(self, root, l, r):

		def f(root, l, r):
			if not root:
				return root
			if root.data >= l and root.data <= r:
				root.left = f(root.left, l, r)
				root.right = f(root.right, l, r)
			elif root.data < l:
				return f(root.right, l, r)
			else:
				return f(root.left, l, r)
			return root
		return f(root, l, r)


class Solution:

	def removekeys(self, root, l, r):
		while root and (l > root.data or r < root.data):
			if root.data > r:
				root = root.left
			elif root.data < l:
				root = root.right
		self.helper(root, l, r)
		return root

	def helper(self, root, l, r):
		if root is None:
			return
		while root.right and root.right.data > r:
			root.right = root.right.left
		while root.left and root.left.data < l:
			root.left = root.left.right
		self.helper(root.left, l, r)
		self.helper(root.right, l, r)
		return


class Solution:

	def removekeys(self, root, l, r):

		def trim(node):
			if not node:
				return None
			elif node.data > r:
				return trim(node.left)
			elif node.data < l:
				return trim(node.right)
			else:
				node.left = trim(node.left)
				node.right = trim(node.right)
				return node
		return trim(root)


class Solution:

	def postorder(self, root, parent, brange, order):
		if root is None:
			return
		self.postorder(root.left, root, brange, order)
		self.postorder(root.right, root, brange, order)
		rem = root.data < brange[0] or root.data > brange[1]
		order.append([root, parent, rem])

	def removeNodes(self, root, path):
		for n in path:
			if n[2]:
				parent = n[1]
				node = n[0]
				if parent is None:
					if node.left and node.right:
						print('both left and right nodes - impossible to remove')
						return None
					if node.left:
						root = node.left
						node.left = None
					elif node.right:
						root = node.right
						node.right = None
					else:
						root = None
				else:
					pattach = '?'
					if parent.right and parent.right.data == node.data:
						pattach = 'R'
					elif parent.left and parent.left.data == node.data:
						pattach = 'L'
					if pattach == 'R':
						if node.right:
							parent.right = node.right
							node.right = None
						elif node.left:
							parent.right = node.left
							node.left = None
						else:
							parent.right = None
					elif pattach == 'L':
						if node.right:
							parent.left = node.right
							node.right = None
						elif node.left:
							parent.left = node.left
							node.left = None
						else:
							parent.left = None
					if node.left:
						if pattach == 'R':
							parent.right.left = node.left
							node.left = None
						elif pattach == 'L':
							parent.left.left = node.left
							node.left = None
		return root

	def removekeys(self, root, l, r):
		brange = [l, r]
		path = []
		self.postorder(root, None, brange, path)
		return self.removeNodes(root, path)


class Solution:

	def __init__(self):
		self.arr = []
		self.tree = None

	def inorder(self, root, mini, maxi):
		if root.left != None:
			self.inorder(root.left, mini, maxi)
		if root.data >= mini and root.data <= maxi:
			self.arr.append(root.data)
		if root.right != None:
			self.inorder(root.right, mini, maxi)

	def makebst(self, arr, low, high, node=None, side='ro'):
		if low > high:
			return
		mid = low + (high - low) // 2
		nde = Node(arr[mid])
		if side == 'ro':
			self.tree = nde
		if side == 'l':
			node.left = nde
		if side == 'r':
			node.right = nde
		self.makebst(arr, low, mid - 1, nde, 'l')
		self.makebst(arr, mid + 1, high, nde, 'r')

	def removekeys(self, root, l, r):
		self.inorder(root, l, r)
		low = 0
		high = len(self.arr) - 1
		self.makebst(self.arr, low, high)
		return self.tree


class Solution:

	def removekeys(self, root, l, r):
		if root is None:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l:
			if root.right is not None:
				root = root.right
			else:
				root = None
		if root and root.data > r:
			if root.left is not None:
				root = root.left
			else:
				root = None
		return root


class Solution:

	def removekeys(self, root, l, r):
		head = None
		head = self.inorder(root, head, l, r)
		return head

	def inorder(self, root, head, l, r):
		if not root:
			return
		if l <= root.data <= r:
			head = root
			head.left = self.inorder(root.left, head.left, l, r)
			head.right = self.inorder(root.right, head.right, l, r)
			return head
		elif r < root.data:
			head = self.inorder(root.left, head, l, r)
			return head
		elif l > root.data:
			head = self.inorder(root.right, head, l, r)
			return head


class Solution:

	def removekeys(self, root, l, r):
		if not root:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l or root.data > r:
			root = delete(root)
		return root

def delete(root):
	if not root.left and (not root.right):
		root = None
	elif not root.left:
		root = root.right
	elif not root.right:
		root = root.left
	else:
		temp = find(root.left)
		root.data = temp.data
		root = delete(temp)
	return root

def find(root):
	while root.right:
		root = root.right
	return root


class Solution:

	def removekeys(self, root, l, r):

		def dfs(root, l, r):
			if not root:
				return
			root.left = dfs(root.left, l, r)
			root.right = dfs(root.right, l, r)
			if root.data < l:
				return root.right
			elif root.data > r:
				return root.left
			return root
		return dfs(root, l, r)


class Solution:

	def removekeys(self, root, l, h):
		if root == None:
			return None
		if root.data > h:
			return self.removekeys(root.left, l, h)
		if root.data < l:
			return self.removekeys(root.right, l, h)
		root.left = self.removekeys(root.left, l, h)
		root.right = self.removekeys(root.right, l, h)
		return root


def f(node, l, r):
	if node is None:
		return None
	node.left = f(node.left, l, r)
	node.right = f(node.right, l, r)
	if node.data < l:
		out = node.right
		node = None
		return out
	if node.data > r:
		out = node.left
		node = None
		return out
	return node

class Solution:

	def removekeys(self, root, l, r):
		return f(root, l, r)


def fun(root, mini, maxi):
	if root == None:
		return None
	elif root.data < mini:
		while root != None and root.data < mini:
			root = root.right
		return fun(root, mini, maxi)
	elif root.data > maxi:
		while root != None and root.data > maxi:
			root = root.left
		return fun(root, mini, maxi)
	else:
		root.left = fun(root.left, mini, maxi)
		root.right = fun(root.right, mini, maxi)
		return root

class Solution:

	def removekeys(self, root, l, r):
		return fun(root, l, r)


def removeKeysHelper(root, l, r):
	if not root:
		return None
	root.left = removeKeysHelper(root.left, l, r)
	root.right = removeKeysHelper(root.right, l, r)
	if root.data < l:
		rChild = root.right
		root = None
		return rChild
	if root.data > r:
		lChild = root.left
		root = None
		return lChild
	return root

class Solution:

	def removekeys(self, root, l, r):
		return removeKeysHelper(root, l, r)


class Solution:

	def f(self, root, l, r):
		if root == None:
			return root
		if root.data >= l and root.data <= r:
			x = self.f(root.left, l, r)
			y = self.f(root.right, l, r)
			root.left = x
			root.right = y
			return root
		if root.data > r:
			x = self.f(root.left, l, r)
			root.left = x
			root.right = None
			return x
		if root.data < l:
			x = self.f(root.right, l, r)
			root.left = None
			root.right = x
			return x

	def removekeys(self, root, l, r):
		x = self.f(root, l, r)
		return x


class Solution:

	def removekeys(self, root, l, r):

		def remove(root, l, r):
			if root == None:
				return None
			root.left = remove(root.left, l, r)
			root.right = remove(root.right, l, r)
			if root.data < l:
				child = root.right
				return child
			elif root.data > r:
				child = root.left
				return child
			return root
		root = remove(root, l, r)
		return root


class Solution:

	def removekeys(self, root, l, r):

		def _replace(par, nd, sub):
			if par.left == nd:
				par.left = sub
			else:
				par.right = sub

		def _solve(nd, par):
			if not nd:
				return
			if nd.data < l:
				_replace(par, nd, nd.right)
				_solve(nd.right, par)
			elif nd.data > r:
				_replace(par, nd, nd.left)
				_solve(nd.left, par)
			else:
				_solve(nd.left, nd)
				_solve(nd.right, nd)
		guard = Node(-10 ** 9)
		guard.right = root
		nd = root
		_solve(nd, guard)
		return guard.right


class Solution:

	def removekeys(self, root, minn, maxx):
		if root is None:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < minn:
			return root.right
		elif root.data > maxx:
			return root.left
		return root


class Solution:

	def removekeys(self, root, l, r):
		if root is None:
			return None
		if root.left is None and root.right is None:
			if root.data < l or root.data > r:
				return None
			else:
				return root
		if root.data < l:
			return self.removekeys(root.right, l, r)
		if root.data > r:
			return self.removekeys(root.left, l, r)
		if root.left:
			root.left = self.removekeys(root.left, l, r)
		if root.right:
			root.right = self.removekeys(root.right, l, r)
		return root
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def printInorder(root):
	if root:
		printInorder(root.left)
		print(root.data, end=' ')
		printInorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		inp = list(map(int, input().split()))
		l = inp[0]
		r = inp[1]
		s = input()
		root = buildTree(s)
		ob = Solution()
		head = ob.removekeys(root, l, r)
		printInorder(head)
		print()


class Solution:

	def removekeys(self, root, l, r):
		if root == None:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l:
			rc = root.right
			return rc
		if root.data > r:
			lc = root.left
			return lc
		return root


class Solution:
	l = []
	t = []

	def removekeys(self, root, l, r):
		if root == None:
			return None
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l:
			rchild = root.right
			return rchild
		if root.data > r:
			lchild = root.left
			return lchild
		return root


class Solution:

	def helper(self, node, l, r):
		if node == None:
			return node
		h1 = self.helper(node.left, l, r)
		h2 = self.helper(node.right, l, r)
		node.left = None
		node.right = None
		if node.data < l or node.data > r:
			if h1 == None and h2 == None:
				return None
			if h1 == None:
				return h2
			if h2 == None:
				return h1
			cur = h2
			while cur.left != None:
				cur = cur.left
			cur.left = h1
			return h2
		if h1 == None and h2 == None:
			return node
		if h2 == None:
			node.left = h1
			return node
		if h1 == None:
			node.right = h2
			return node
		node.left = h1
		node.right = h2
		return node

	def removekeys(self, root, l, r):
		return self.helper(root, l, r)


class Solution:

	def create(self, l1, r1, arr2):
		if l1 > r1:
			return None
		m = (l1 + r1) // 2
		root = Node(arr2[m])
		root.left = self.create(l1, m - 1, arr2)
		root.right = self.create(m + 1, r1, arr2)
		return root

	def inorder(self, root, arr):
		if root == None:
			return None
		self.inorder(root.left, arr)
		arr.append(root.data)
		self.inorder(root.right, arr)

	def removekeys(self, root, l, r):
		arr1 = []
		arr2 = []
		self.inorder(root, arr1)
		for i in arr1:
			if i <= r and i >= l:
				arr2.append(i)
		l1 = 0
		r1 = len(arr2) - 1
		return self.create(l1, r1, arr2)


class Solution:

	def inot(self, root, l, r):
		if not root:
			return []
		st = []
		res = []
		curr = root
		while True:
			if curr:
				st.append(curr)
				curr = curr.left
			elif st:
				curr = st.pop()
				if curr.data in range(l, r + 1):
					res.append(curr.data)
				curr = curr.right
			else:
				break
		root1 = None
		for elem in res:
			root1 = self.constructBST(root1, elem)
		return root1

	def hbBST(self, arr, s, e):
		if s > e:
			return
		m = (s + e) // 2
		root = Node(arr[m])
		root.left = self.hbBST(arr, s, m - 1)
		root.right = self.hbBST(arr, m + 1, e)
		return root

	def constructBST(self, root, item):
		if not root:
			return Node(item)
		if item < root.data:
			root.left = self.constructBST(root.left, item)
		elif item > root.data:
			root.right = self.constructBST(root.right, item)
		return root

	def removekeys(self, root, l, r):
		if not root:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data < l:
			return root.right
		elif root.data > r:
			return root.left
		return root


class Solution:

	def removekeys(self, root, l, r):
		if root is None:
			return
		root.left = self.removekeys(root.left, l, r)
		root.right = self.removekeys(root.right, l, r)
		if root.data not in range(l, r + 1):
			if root.data < l:
				return root.right
			elif root.data > l:
				return root.left
		return root


class Solution:

	def removekeys(self, root, Min, Max):
		if root == None:
			return None
		root.left = self.removekeys(root.left, Min, Max)
		root.right = self.removekeys(root.right, Min, Max)
		if root.data < Min:
			rChild = root.right
			return rChild
		if root.data > Max:
			lChild = root.left
			return lChild
		return root


class Solution:

	def removekeys(self, root, l, r):
		return self.helper(root, l, r)

	def helper(self, root, l, r):
		if root is None:
			return None
		if root.data < l:
			return self.helper(root.right, l, r)
		elif root.data > r:
			return self.helper(root.left, l, r)
		else:
			left_node = self.helper(root.left, l, r)
			right_node = self.helper(root.right, l, r)
			root.left = left_node
			root.right = right_node
			return root