Given a BST and a value k, the task is to delete the nodes having values greater than or equal to k.
Example 1:
Input:
    4   
   / \  
  1   9 
k = 2 
Output:
1
Your Task:
The task is to complete the function deleteNode() which takes root, k as the argument, and returns the root of tree after deleting values greater than or equal to k. The driver code will print the inorder traversal of the updated tree in output itself. 
Expected Time Complexity: O(Size of tree)
Expected Auxiliary Space: O(1).
Constraints:
1 <= T <= 100
1 <= N <= 10^{3}
1 <= A[] <= 10^{3}
1 <= k <= N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

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:

    # your task is to complete this function

    # function should delete all the Nodes greater than or equal to k

    # function should return the new head to pointer

    def deleteNode(self, root, k):

        # Code here

Solutions:
class Solution:

	def deleteNode(self, root, k):
		return self.helper(root, k) or root

	def deleteNodeHelper(self, root):
		if root is None:
			return
		if root.left is None and root.right is None:
			del root
			return
		self.deleteNodeHelper(root.left)
		self.deleteNodeHelper(root.right)

	def helper(self, root, k):
		if root is None:
			return None
		if root.data >= k:
			newRoot = root.left
			self.deleteNodeHelper(root.right)
			del root
			return self.helper(newRoot, k)
		else:
			rightChild = self.helper(root.right, k)
			root.right = rightChild
			return root


class Solution:

	def deleteNode(self, root, k):
		if root == None:
			return
		if root.data >= k:
			return self.deleteNode(root.left, k)
		if root.data < k:
			root.right = self.deleteNode(root.right, k)
			return root


class Solution:

	def Delete(self, root, k):
		if root == None:
			return None
		l = self.Delete(root.left, k)
		r = self.Delete(root.right, k)
		if root.data < k:
			root.left = l
			root.right = r
			return root
		else:
			return l

	def deleteNode(self, root, k):
		root = self.Delete(root, k)
		return root


class Solution:

	def inorder1(self, root):
		if root is None:
			return
		print(root.data)
		self.inorder1(root.left)
		print(root.data)
		self.inorder1(root.right)
		print(root.data)

	def inorder(self, root, k):
		if root is None:
			return
		if root.left is None or root.right is None:
			return
		self.inorder(root.left, k)
		if root.right.data > k:
			root.right = None
			print('right')
		if root.left.data > k:
			self.inorder(root, k)
			print('left')
		else:
			print('left1')
			root.left = None
		self.inorder(root.right, k)

	def deleteNode(self, root, k):
		if root is None:
			return
		if root.data >= k:
			return self.deleteNode(root.left, k)
		root.right = self.deleteNode(root.right, k)
		return root


class Solution:

	def root_lefts(self, root):
		while root.right:
			root = root.right
		return root

	def util(self, root, x):
		if not root:
			return root
		if root.data == x:
			return root.left
		if root.data > x:
			return self.util(root.left, x)
		if root.data < x:
			root.right = self.util(root.right, x)
		return root

	def deleteNode(self, root, k):
		return self.util(root, k)


class Solution:

	def deleteNode(self, root, k):
		while root and root.data >= k:
			root = root.left
		start = root
		while root:
			while root.right and root.right.data >= k:
				root.right = root.right.left
			root = root.right
		return start


class Solution:

	def deleteNode(self, root, k):
		nod = Node(0)

		def fun2(root):
			if root == None:
				return
			if root.data >= k:
				return fun2(root.left)
			root.right = fun2(root.right)
			return root
		return fun2(root)


class Solution:

	def deleteNode(self, root, k):

		def f(root, k):
			if not root:
				return None
			if root.data < k:
				root.right = f(root.right, k)
			else:
				root = f(root.left, k)
			return root
		return f(root, k)


class Solution:

	def __init__(self):
		self.inorder = []

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

	def MakeTree(self, inorder):
		if inorder == []:
			return None
		mid = len(inorder) // 2
		root = Node(inorder[mid])
		root.left = self.MakeTree(inorder[:mid])
		root.right = self.MakeTree(inorder[mid + 1:])
		return root

	def deleteNode(self, root, k):
		self.InOrder(root)
		for i in range(0, len(self.inorder)):
			if self.inorder[i] < k:
				continue
			else:
				self.inorder = self.inorder[:i]
				break
		return self.MakeTree(self.inorder)


class Solution:

	def solve(self, root, k):
		if root == None:
			return None
		elif root.data >= k:
			l = self.solve(root.left, k)
			return l
		else:
			root.right = self.solve(root.right, k)
			return root

	def deleteNode(self, root, k):
		res = self.solve(root, k)
		return res


class Solution:

	def deleteNode(self, root, k):
		head = None
		head = self.delete(root, k, head)
		return head

	def delete(self, root, k, head):
		if not root:
			return
		if root.data < k:
			head = root
			head.left = self.delete(root.left, k, head.left)
			head.right = self.delete(root.right, k, head.right)
		else:
			head = self.delete(root.left, k, head)
		return head


class Solution:

	def deleteNode(self, root, k):
		a = []
		b = []
		x = self.pre(root, a)
		a.sort()
		for i in a:
			if i < k:
				b.append(i)
		for i in b:
			print(i, end=' ')

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


def deep(root):
	cur = root
	while cur.left != None:
		cur = cur.left
	return cur

def delete(root, key):
	if root is None:
		return None
	if root.data > key:
		root.left = delete(root.left, key)
	elif root.data < key:
		root.right = delete(root.right, key)
	else:
		if root.left is None:
			temp = root.right
			root = None
			return temp
		if root.right is None:
			temp = root.left
			root = None
			return temp
		temp = deep(root.right)
		root.data = temp.data
		root.right = delete(root.right, temp.data)
	return root

class Solution:

	def inorder(self, root):
		res = []
		q = []
		cur = root
		while True:
			if cur is not None:
				q.append(cur)
				cur = cur.left
			elif q:
				cur = q.pop()
				res.append(cur.data)
				cur = cur.right
			else:
				break
		return res

	def deleteNode(self, root, k):
		ino = self.inorder(root)
		for i in ino:
			if i >= k:
				root = delete(root, i)
		return root


class Solution:

	def deleteNode(self, root, k):
		if not root:
			return
		root.left = self.deleteNode(root.left, k)
		root.right = self.deleteNode(root.right, k)
		if root.data >= k:
			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 = minn(root.left)
		root.data = temp.data
		temp = delete(temp)
	return root

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


class Delete:

	def getNodeAndParent(self, root, key):
		parent = None
		tmp = root
		while tmp:
			if tmp.data == key:
				return [tmp, parent]
			parent = tmp
			if tmp.data > key:
				tmp = tmp.left
			else:
				tmp = tmp.right
		return [None, None]

	def isLeaf(self, node):
		return not node.left and (not node.right)

	def deleteLeaf(self, node, parent):
		if parent.left == node:
			parent.left = None
		else:
			parent.right = None
		return node

	def isSingleChildNode(self, node):
		return not node.left and node.right or (node.left and (not node.right))

	def deleteSingleChildNode(self, node, parent):
		if node.left:
			if parent.left == node:
				parent.left = node.left
			else:
				parent.right = node.left
			node.left = None
		else:
			if parent.left == node:
				parent.left = node.right
			else:
				parent.right = node.right
			node.right = None
		return node

	def deleteDoubleChildNode(self, node, parent):
		re_parent = node
		re_node = node.left
		while re_node.right:
			re_parent = re_node
			re_node = re_node.right
		if self.isLeaf(re_node):
			removed_node = self.deleteLeaf(re_node, re_parent)
		else:
			removed_node = self.deleteSingleChildNode(re_node, re_parent)
		if parent:
			if parent.left == node:
				parent.left = removed_node
			else:
				parent.right = removed_node
		removed_node.left = node.left
		removed_node.right = node.right
		return node

	def deleteRoot(self, root):
		if self.isLeaf(root):
			new_root = None
		elif self.isSingleChildNode(root):
			if root.left:
				new_root = root.left
			else:
				new_root = root.right
		else:
			new_root = root.left
			while new_root.right:
				new_root = new_root.right
			root = self.deleteDoubleChildNode(root, None)
		del root
		return new_root

	def deleteNodeBST(self, root, key: int):
		(node, parent) = self.getNodeAndParent(root, key)
		if not node:
			return root
		if not parent:
			root = self.deleteRoot(root)
		else:
			if self.isLeaf(node):
				removed_node = self.deleteLeaf(node, parent)
			elif self.isSingleChildNode(node):
				removed_node = self.deleteSingleChildNode(node, parent)
			else:
				removed_node = self.deleteDoubleChildNode(node, parent)
			del removed_node
		return root

class Solution:

	def __init__(self) -> None:
		self.values = []

	def getVals(self, root, k):
		if not root:
			return
		if root.data >= k:
			self.values.append(root.data)
		self.getVals(root.left, k)
		self.getVals(root.right, k)

	def deleteNode(self, root, k):
		delete_node = Delete()
		self.getVals(root, k)
		for key in self.values:
			root = delete_node.deleteNodeBST(root, key)
		return root


class Solution:

	def deleteNode(self, root, k):
		if root == None:
			return root
		if root.data == k:
			return root.left
		elif root.data > k:
			temp = root.left
			return self.deleteNode(temp, k)
		else:
			root.right = self.deleteNode(root.right, k)
			return root


class Solution:

	def deleteNode(self, node, k):
		if node is None:
			return node
		node.left = self.deleteNode(node.left, k)
		node.right = self.deleteNode(node.right, k)
		if node.data >= k:
			return node.left
		return node


class Solution:

	def deleteNode(self, root, k):
		if root == None:
			return
		if root.data >= k:
			return self.deleteNode(root.left, k)
		root.left = self.deleteNode(root.left, k)
		root.right = self.deleteNode(root.right, k)
		return root

	def delete(self, root):
		if root == None:
			return
		if root.left:
			root.data = root.left.data
			root.left = self.delete(root.left)
		elif root.right:
			root.data = root.right.data
			root.right = self.delete(root.right)
		else:
			del root
			return


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def ino(self, r, l, k):
		if r is not None:
			self.ino(r.left, l, k)
			if r.data < k:
				l.append(Node(r.data))
			self.ino(r.right, l, k)

	def deleteNode(self, root, k):
		l = []
		self.ino(root, l, k)
		n = len(l)
		for i in range(n - 1):
			l[i].right = l[i + 1]
		return l[0]


node = None

class Solution:

	def solve(self, root, k):
		if root is None:
			return None
		global head, itr
		if k <= root.data:
			if itr:
				itr.right = root.left
			self.solve(root.left, k)
		else:
			if head is None:
				head = root
				itr = head
			else:
				itr.right = root
				itr = root
			self.solve(root.right, k)

	def deleteNode(self, root, k):
		global head, itr
		head = itr = None
		self.solve(root, k)
		return head


class Solution:

	def deleteNode(self, root, k):
		if root:
			if root.data < k:
				root.right = self.deleteNode(root.right, k)
			else:
				root = root.left
				root = self.deleteNode(root, k)
		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 traverseInorder(root):
	if root is not None:
		traverseInorder(root.left)
		print(root.data, end=' ')
		traverseInorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		root = buildTree(s)
		k = int(input())
		R = Solution().deleteNode(root, k)
		traverseInorder(R)
		print()


class Solution:

	def deleteNode(self, root, k):
		if not root:
			return root
		if root.data < k:
			root.right = self.deleteNode(root.right, k)
			return root
		elif root.data > k:
			return self.deleteNode(root.left, k)
		else:
			return root.left


class Solution:

	def deleteNode(self, root, k):
		a = []
		arr = inorder(root, a)
		for i in arr:
			if i >= k:
				w = deleteS(root, i)
			else:
				w = root
		return w

def deleteS(root, k):
	if root is None:
		return root
	if root.data > k:
		root.left = deleteS(root.left, k)
	elif root.data < k:
		root.right = deleteS(root.right, k)
	else:
		if root.left is None:
			temp = root.right
			root = None
			return temp
		if root.right is None:
			temp = root.left
			root = None
			return temp
		temp = minValueNode(root.right)
		root.data = temp.data
		root.right = deleteS(root.right, temp.data)
	return root

def minValueNode(node):
	current = node
	while current.left is not None:
		current = current.left
	return current

def inorder(root, a):
	if root is not None:
		inorder(root.left, a)
		a.append(root.data)
		inorder(root.right, a)
	return a


class Node:

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

class Solution:

	def deleteNode(self, root, k):
		if root is None:
			return
		root.left = self.deleteNode(root.left, k)
		root.right = self.deleteNode(root.right, k)
		if root.data >= k:
			temp = root.left
			root = None
			return temp
		return root


class Solution:

	def __init__(self):
		self.root = None

	def deleteNode(self, root, k):
		self.root = root
		return self.__delete_k_greater(root, key=k)

	def __delete_k_greater(self, node, key):
		if node and node.data >= key:
			if node == self.root:
				node = self.root = self.root.left
			else:
				node = node.left
			if node:
				return self.__delete_k_greater(node, key)
		elif node and node.data < key and node.right:
			node.right = self.__delete_k_greater(node.right, key)
			return node
		else:
			return node


class Solution:

	def deleteNode(self, root, k):
		newRoot = self.searchForNewRoot(root, k)
		if newRoot == None:
			return None
		self.trimTree(newRoot, k)
		return newRoot

	def searchForNewRoot(self, root, k):
		curr = root
		while curr.data >= k:
			if curr.left == None:
				return None
			curr = curr.left
		return curr

	def trimTree(self, root, k):
		curr = root
		parent = None
		while curr != None:
			if curr.data >= k:
				parent.right = curr.left
				curr = curr.left
			else:
				parent = curr
				curr = curr.right


class Solution:

	def deleteNode(self, root, k):
		while root.data >= k:
			if root.left == None and root.right == None:
				return
			root = root.left
		temp = root
		prev = None
		while temp != None:
			if temp.data < k:
				prev = temp
				temp = temp.right
			else:
				prev.right = temp.left
				temp = temp.left
		return root