Given a Binary Tree of size N, your task is to complete the function deletionBT(), that should delete a given node from the tree by making sure that tree shrinks from the bottom (the deleted node is replaced by bottommost and rightmost node).
Example:
Your Task:
You don't have to take input. Complete the function deletionBT() that takes root node of the tree and given node value (Key) as input parameter and return the root of the modified tree.
Example 1:
 
Input:
Key=1
         1
       /   \
      4     7
     / \
    5   6 
Output:
5 4 6 7 
Explanation:
Modified Tree after deletion the 
node with key = 1
     6 
    /  \
   4    7
  /   
 5     
The Inorder traversal of the modified 
tree is 5 4 6 7 
Constraints:
1<=N<=10^{4}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3



def deletionBT(root, key):

    '''

    root: root of tree

    key:  key to be deleted

    return: root after deleting 

    '''

    

    



Solutions:
def deleteDeepest(root, d_node):
	queue = []
	queue.append(root)
	while len(queue):
		temp = queue.pop(0)
		if temp is d_node:
			temp = None
			return
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				queue.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				queue.append(temp.left)

def deletionBT(root, key):
	if root is None:
		return None
	if root.left is None and root.right is None:
		if root.data == key:
			return None
		else:
			return root
	key_node = None
	temp = None
	queue = []
	queue.append(root)
	while len(queue):
		temp = queue.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			queue.append(temp.left)
		if temp.right:
			queue.append(temp.right)
	if key_node:
		x = temp.data
		deleteDeepest(root, temp)
		key_node.data = x
	return root


def deletionBT(root, key):
	l = [root]
	res = [root.data]
	while l:
		r = []
		for i in l:
			if i.left:
				r.append(i.left)
				res.append(i.left.data)
			if i.right:
				r.append(i.right)
				res.append(i.right.data)
		l = r
	lastleaf = res[-1]

	def helper(root, lastleaf):
		if root == None:
			return
		if root.data == key:
			root.data = lastleaf
		if root.left != None and root.left.data == lastleaf:
			root.left = None
		if root.right != None and root.right.data == lastleaf:
			root.right = None
		helper(root.left, lastleaf)
		helper(root.right, lastleaf)
		return
	helper(root, lastleaf)
	return root


def fun(root, level, l):
	if root == None:
		return
	if level >= len(l):
		l.append([])
	l[level].append(root)
	fun(root.left, level + 1, l)
	fun(root.right, level + 1, l)

def fun2(root, key, pos):
	if root == None:
		return
	if root.data == key:
		root.data = pos.data
	fun2(root.left, key, pos)
	fun2(root.right, key, pos)

def fun1(root, pos):
	if root == None:
		return
	if root.left == pos:
		root.left = None
	elif root.right == pos:
		root.right = None
	fun1(root.left, pos)
	fun1(root.right, pos)

def deletionBT(root, key):
	l = []
	fun(root, 0, l)
	pos = l[-1][-1]
	fun2(root, key, pos)
	if root == pos:
		root = None
	fun1(root, pos)
	return root


def deletionBT(root, key):

	def deleteDeepest(root, delete_node):
		q = []
		q.append(root)
		while q:
			temp = q.pop(0)
			if temp is delete_node:
				temp = None
				return
			if temp.right:
				if temp.right is delete_node:
					temp.right = None
					return
				else:
					q.append(temp.right)
			if temp.left:
				if temp.left is delete_node:
					temp.left = None
					return
				else:
					q.append(temp.left)

	def deletion(root, key):
		if root == None:
			return None
		if root.left == None and right.right == None:
			if root.key == key:
				return None
			else:
				return root
		key_node = None
		q = []
		q.append(root)
		temp = None
		while q:
			temp = q.pop(0)
			if temp.data == key:
				key_node = temp
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		if key_node:
			x = temp.data
			deleteDeepest(root, temp)
			key_node.data = x
		return root
	return deletion(root, key)


def deletionBT(root, key):
	stack = [root]
	parent = {root: None}
	node = None
	target = None
	while stack:
		top = stack.pop(0)
		node = top
		if top.data == key:
			target = top
		if top.left:
			parent[top.left] = top
			stack.append(top.left)
		if top.right:
			parent[top.right] = top
			stack.append(top.right)
	target.data = node.data
	if node == parent[node].left:
		parent[node].left = None
	else:
		parent[node].right = None
	return root


from collections import deque

def deletionBT(root, key):
	q = deque([root])
	cur = None
	pre = None
	node = None
	while q:
		cur = q.popleft()
		if cur.data == key:
			node = cur
		if cur.left:
			pre = cur
			q.append(cur.left)
		if cur.right:
			pre = cur
			q.append(cur.right)
	node.data = cur.data
	if pre.right:
		pre.right = None
	else:
		pre.left = None
	return root


def deepest(root, k):
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp is k:
			temp = None
			return
		if temp.right:
			if temp.right is k:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is k:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root == None:
		return
	if root.left == None and root.right == None:
		if root.data == key:
			root = None
			return
	new_node = None
	q = []
	q.append(root)
	temp = None
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			new_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if new_node:
		x = temp.data
		deepest(root, temp)
		new_node.data = x
	return root


def deletionBT(root, key):
	q = []
	lastnode = None
	temp = None
	q.append(root)
	while q:
		node = q.pop(0)
		if node.data == key:
			temp = node
		if node.left:
			lastnode = node
			q.append(node.left)
		if node.right:
			lastnode = node
			q.append(node.right)
	if lastnode.right:
		temp.data = lastnode.right.data
		lastnode.right = None
	else:
		temp.data = lastnode.left.data
		lastnode.left = None
	return root


def deletionBT(root, key):
	q = []
	q.append(root)
	level = []
	while q:
		qlen = len(q)
		lvl = []
		for i in range(qlen):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			lvl.append(node)
		level.append(lvl)
	repkey = level[-1][-1].data

	def dfsrem(node):
		if not node:
			return
		if node.left and node.left.data == repkey:
			node.left = None
			return
		elif node.right and node.right.data == repkey:
			node.right = None
			return
		dfsrem(node.left)
		dfsrem(node.right)
	dfsrem(root)

	def dfs(node):
		if node.data == key:
			node.data = repkey
			return
		if node.left:
			dfs(node.left)
		if node.right:
			dfs(node.right)
	dfs(root)
	return root


from collections import deque

def Preorder(root, prev, par, node, key):
	if root == None:
		return
	if root.data == key:
		node[0] = root
		par[0] = prev
		return
	Preorder(root.left, root, par, node, key)
	Preorder(root.right, root, par, node, key)

def deletionBT(root, key):
	node = [None]
	par = [None]
	Preorder(root, None, par, node, key)
	last = None
	dq = deque()
	dq.append(root)
	while len(dq) > 0:
		temp = dq.popleft()
		last = temp
		if temp.left != None:
			dq.append(temp.left)
		if temp.right != None:
			dq.append(temp.right)
	n1 = node[0]
	par[0] = None
	node[0] = None
	Preorder(root, None, par, node, last.data)
	if par[0].left != None and par[0].left.data == last.data:
		par[0].left = None
	else:
		par[0].right = None
	n1.data = last.data
	return root


def deldeepest(root, delnode):
	q = []
	q.append(root)
	while q != []:
		temp = q.pop(0)
		if temp == delnode:
			temp = None
			return
		if temp.left:
			if temp.left == delnode:
				temp.left = None
				return
			else:
				q.append(temp.left)
		if temp.right:
			if temp.right == delnode:
				temp.right = None
				return
			else:
				q.append(temp.right)

def deletionBT(root, key):
	if root == None:
		return None
	if root.left == None and root.left == None:
		if root.data == key:
			return
		else:
			return root
	q = []
	q.append(root)
	while q:
		temp = q.pop(0)
		if temp.data == key:
			keyn = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if keyn:
		x = temp.data
		deldeepest(root, temp)
		keyn.data = x
	return root


def deletionBT(root, key):
	if root == None:
		return
	q = []
	q.append(root)
	x = None
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			x = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if x:
		new = temp.data
		helper(root, temp.data)
		x.data = new
	return root

def helper(root, key):
	if root == None:
		return
	if root.left and root.left.data == key:
		root.left = None
		return
	if root.right and root.right.data == key:
		root.right = None
		return
	helper(root.left, key)
	helper(root.right, key)


def deletionBT(root, key):
	if root == None:
		return None
	if root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return root
	key_node = None
	temp = None
	last = None
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			last = temp
			q.append(temp.left)
		if temp.right:
			last = temp
			q.append(temp.right)
	if key_node != None:
		key_node.data = temp.data
		if last.right == temp:
			last.right = None
		else:
			last.left = None
	return root


def deletionBT(root, key):
	item = traversal(root, 0, [])[-1][-1]
	helper(root, key, item)
	return root

def traversal(root, level, arr):
	if root is None:
		return
	if level == len(arr):
		arr.append([])
	arr[level].append(root.data)
	traversal(root.left, level + 1, arr)
	traversal(root.right, level + 1, arr)
	return arr

def helper(root, key, item):
	if root is None:
		return
	if root.data == key:
		root.data = item
	if root.left and root.left.data == item:
		root.left = None
	if root.right and root.right.data == item:
		root.right = None
	helper(root.left, key, item)
	helper(root.right, key, item)
	return


def deletionBT(root, key):
	q = []
	q.append(root)
	p_node = None
	r_node = None
	while len(q):
		temp = q[0]
		q.pop(0)
		if temp.data == key:
			r_node = temp
		if temp.left:
			q.append(temp.left)
			p_node = temp
		if temp.right:
			q.append(temp.right)
			p_node = temp
	if p_node.right:
		r_node.data = p_node.right.data
		p_node.right = None
	else:
		r_node.data = p_node.left.data
		p_node.left = None


def deletionBT(root, key):
	queue = [root]
	while len(queue) > 0:
		temp = queue[0]
		if temp.data == key:
			delete = temp
		if temp.left:
			queue.append(temp.left)
		if temp.right:
			queue.append(temp.right)
		queue.pop(0)
	br = temp
	delete.data = br.data
	queue = [root]
	while len(queue) > 0:
		temp = queue[0]
		if temp.left == br:
			temp.left = None
			break
		elif temp.right == br:
			temp.right = None
			break
		if temp.left:
			queue.append(temp.left)
		if temp.right:
			queue.append(temp.right)
		queue.pop(0)
	return root


def deletionBT(root, key):
	A = []
	B = []
	C = []
	D = []
	if root is None:
		return A
	A.append(root)
	while len(A) > 0:
		while len(A) > 0:
			node = A.pop(0)
			B.append(node.data)
			if node.left is not None:
				D.append(node.left)
			if node.right is not None:
				D.append(node.right)
		A.extend(D)
		D = []
		C.append(B)
		B = []
	Q = []
	p = 0
	p = C[-1][-1]
	if root.data == p:
		return root
	else:
		delete(root, p)
		if root.data == key:
			root.data = p
			return root
		else:
			findnchange(root, key, p)
			return root

def findnchange(root, key, p):
	if root.left:
		if root.left.data == key:
			root.left.data = p
			return 1
		elif findnchange(root.left, key, p) == 1:
			return 1
	if root.right:
		if root.right.data == key:
			root.right.data = p
			return 1
		elif findnchange(root.right, key, p) == 1:
			return 1

def delete(root, p):
	if root.left:
		if root.left.data == p:
			root.left = None
			return 1
		elif delete(root.left, p) == 1:
			return 1
	if root.right:
		if root.right.data == p:
			root.right = None
			return 1
		elif delete(root.right, p) == 1:
			return 1


def f(root, n):
	if root == None:
		return
	if root.left and root.left.data == n:
		root.left = None
		return
	if root.right and root.right.data == n:
		root.right = None
		return
	f(root.left, n)
	f(root.right, n)

def deletionBT(root, key):
	q = [root]
	x = None
	while q:
		node = q.pop(0)
		if node.data == key:
			x = node
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)
	if x == None:
		return root
	f(root, node.data)
	x.data = node.data
	return root


reqNode = None
lastParent = None
lastNode = None

def dfs(arr, key):
	global reqNode, lastParent, lastNode
	newArr = []
	for node in arr:
		if node.data == key:
			reqNode = node
		if node.left:
			lastParent = node
			newArr.append(node.left)
		if node.right:
			lastParent = node
			newArr.append(node.right)
	if not newArr:
		lastNode = arr[-1]
	else:
		dfs(newArr, key)

def deletionBT(root, key):
	global reqNode, lastParent, lastNode
	reqNode = None
	lastParent = None
	lastNode = None
	tmpRoot = Node(None)
	tmpRoot.left = root
	dfs([tmpRoot], key)
	reqNode.data = lastNode.data
	if lastParent.right:
		lastParent.right = None
	else:
		lastParent.left = None


def find(root, key):
	if not root:
		return
	if root.data == key:
		return root
	x = find(root.left, key)
	if x:
		return x
	y = find(root.right, key)
	if y:
		return y

def deletionBT(root, key):
	if not root:
		return
	level = 0
	queue = deque([[root, level]])
	vals = {}
	while queue:
		curr = queue.popleft()
		level = curr[1]
		curr = curr[0]
		if level not in vals:
			vals[level] = []
		vals[level].append(curr)
		if curr.left:
			queue.append([curr.left, level + 1])
		if curr.right:
			queue.append([curr.right, level + 1])
	ground = max(vals.keys())
	final = vals[ground][-1]
	parents = vals[ground - 1]
	parent = None
	pos = 0
	for i in parents:
		if i.left == final:
			parent = i
			pos = -1
			break
		elif i.right == final:
			parent = i
			pos = 1
			break
	node = find(root, key)
	node.data = final.data
	if pos == -1:
		parent.left = None
	else:
		parent.right = None
	return root


def deletionBT(root, key):

	def trav_key(head, key):
		val = None
		if head is None:
			return
		if head.data == key:
			return head
		queue = [head]
		while queue:
			temp = queue.pop(0)
			if temp.left:
				queue.append(temp.left)
				val = temp.left
			if temp.right:
				queue.append(temp.right)
				val = temp.right
			if val.data == key:
				return val
			elif temp.data == key:
				return temp
		return None

	def trav(head, parent):
		val = None
		if head is None:
			return
		queue = [head]
		while queue:
			temp = queue.pop(0)
			if temp.left:
				queue.append(temp.left)
				val = temp.left
				parent[val] = ['left', temp]
			if temp.right:
				queue.append(temp.right)
				val = temp.right
				parent[val] = ['right', temp]
		return val
	parent = {}
	last = trav(root, parent)
	key_mod = trav_key(root, key)
	key_mod.data = last.data
	if last in parent and parent[last][0] == 'left':
		parent[last][1].left = None
	elif last in parent and parent[last][0] == 'right':
		parent[last][1].right = None
	return root


def deletionBT(root, key):
	q = []
	q.append(root)
	if root is None:
		return
	keyNode = None
	last = None
	while q:
		temp = q.pop(0)
		if temp.data == key:
			keyNode = temp
		if temp.left:
			last = temp
			q.append(temp.left)
		if temp.right:
			last = temp
			q.append(temp.right)
	if keyNode != None:
		keyNode.data = temp.data
	if last.right == temp:
		last.right = None
	else:
		last.left = None
	return root


def deletionBT(root, key):
	mod = root
	ans = []
	stack = [root]
	Rstack = []
	ans = None
	while stack:
		node = stack.pop(0)
		if node.data == key:
			ans = node
		if node.left:
			Rstack = [node]
			stack.append(node.left)
		if node.right:
			Rstack = [node]
			stack.append(node.right)
	ri = Rstack.pop()
	ans.data = node.data
	if ri.right:
		ri.right = None
	else:
		ri.left = None
	return mod


def deletedeep(root, d_node):
	if root is None:
		return None
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp == d_node:
			temp == None
		if temp.right:
			if temp.right is d_node:
				temp.right = None
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root == None:
		return None
	if root.left == None and root.right == None:
		if root.key == key:
			return None
		else:
			return root
	key_node = None
	q = []
	q.append(root)
	temp = None
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if key_node:
		x = temp.data
		deletedeep(root, temp)
		key_node.data = x
	return root


def del_dnode(root, dnode):
	q = []
	q.append(root)
	while len(q) != 0:
		temp = q[0]
		q.pop(0)
		if temp == dnode:
			temp = None
			return
		if temp.right:
			if temp.right == dnode:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left == dnode:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	q = []
	q.append(root)
	keynode = None
	while len(q) != 0:
		temp = q[0]
		q.pop(0)
		if temp.data == key:
			keynode = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if keynode:
		x = temp.data
		del_dnode(root, temp)
		keynode.data = x
	return root


def deletionBT(root, key):
	q = [(root, -1)]
	rnode = -1
	while q:
		x = q.pop(0)
		node = x[0]
		par = x[1]
		if node.data == key:
			rnode = node
		if node.left:
			q.append((node.left, node))
		if node.right:
			q.append((node.right, node))
	if rnode != -1:
		rnode.data = node.data
	if par.right:
		par.right = None
	else:
		par.left = None
	return root


def search(root, key):
	q = [root]
	while len(q) > 0:
		temp = q.pop(0)
		if temp.data == key:
			return temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)

def deleteDeepest(root, d_node):
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp is d_node:
			temp = None
			return
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root == None:
		return None
	q = [root]
	ans = []
	while len(q) > 0:
		temp = q.pop(0)
		ans.append(temp.data)
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	last = ans[-1]
	deleteDeepest(root, temp)
	if last == key:
		return root
	temp = search(root, key)
	temp.data = last
	return root


def deletionBT(root, key):
	if root == None:
		return None
	elif root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return None
	q = []
	q.append(root)
	curr = None
	parent = None
	while q:
		curr = q.pop(0)
		if curr.data == key:
			key_node = curr
		if curr.left:
			parent = curr
			q.append(curr.left)
		if curr.right:
			parent = curr
			q.append(curr.right)
	key_node.data = curr.data
	if parent.right == curr:
		parent.right = None
	else:
		parent.left = None
	return root


def deletionBT(root, key):
	if root.data == key and root.left is None and (root.right is None):
		return root
	queue = [root]
	key_node = []
	last = None
	pare_node = 0
	i = None
	while len(queue) > 0:
		temp = queue.pop(0)
		last = temp.data
		if temp.left is not None:
			pare_node = temp
			i = 0
			queue.append(temp.left)
			if temp.left.data == key:
				key_node.append((temp, 0))
		if temp.right is not None:
			pare_node = temp
			i = 1
			queue.append(temp.right)
			if temp.right.data == key:
				key_node.append((temp, 1))
	if root.data == key:
		root.data = last
	else:
		(node, lr) = key_node[0]
		if lr == 0:
			node.left.data = last
		else:
			node.right.data = last
	if i == 0:
		pare_node.left = None
	else:
		pare_node.right = None
		return root


def deletionBT(root, key):
	if not root:
		return None
	if not root.left and (not root.right):
		if root.data == key:
			return None
		else:
			return root
	q = deque()
	q.append(root)
	while q:
		node = q.popleft()
		if node.data == key:
			keynode = node
			break
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)
	t = deque()
	t.append(root)
	parent = None
	while t:
		node = t.popleft()
		if node.left:
			parent = node
			t.append(node.left)
		if node.right:
			parent = node
			t.append(node.right)
	deletenode = node
	keynode.data = deletenode.data
	if deletenode == parent.left:
		parent.left = None
	else:
		parent.right = None
	return root


def deletionBT(root, key):
	keyNode = None
	q = [root]
	while q != []:
		t = q.pop(0)
		if t.data == key:
			keyNode = t
		if t.left:
			last = t
			q.append(t.left)
		if t.right:
			last = t
			q.append(t.right)
	if keyNode:
		keyNode.data = t.data
		if last.left == t:
			last.left = None
		else:
			last.right = None


def deletionBT(root, key):
	if root == None:
		return roon
	if root.left == None and root.right == None:
		if root.data == key:
			root = None
		return root
	q = []
	q.append(root)
	key_node = None
	parent = None
	while len(q) > 0:
		current = q.pop(0)
		if current.data == key:
			key_node = current
		if current.left:
			parent = current
			q.append(current.left)
		if current.right:
			parent = current
			q.append(current.right)
	if not key_node:
		return root
	key_node.data = current.data
	if parent.right:
		parent.right = None
	elif parent.left:
		parent.left = None
	return root


from collections import deque as dq

def deletionBT(root, key):
	g = None
	h = None
	l = []

	def trav(r, k):
		if r == None:
			return
		if r.left and r.left == k:
			r.left = None
		if r.right and r.right == k:
			r.right = None
		trav(r.left, k)
		trav(r.right, k)

	def bfs(r):
		g2 = []
		vis = set()
		vis.add(r)
		q = dq()
		q.append(r)
		while len(q) != 0:
			k = q.popleft()
			if k.data == key:
				g = k
			h = k
			l.append(k)
			if k.left and k.left not in vis:
				g2 = (k, 'l')
				vis.add(k.left)
				q.append(k.left)
			if k.right and k.right not in vis:
				g2 = (k, 'r')
				vis.add(k.right)
				q.append(k.right)
		g.data = l[-1].data
		return g2
	k = bfs(root)
	if k[1] == 'l':
		k[0].left = None
	else:
		k[0].right = None
	return root


def deletionBT(root, key):
	q = [root]
	n = None
	l = None
	while q:
		node = q.pop(0)
		if node.data == key:
			n = node
		if node.left:
			q.append(node.left)
			l = node
		if node.right:
			q.append(node.right)
			l = node
	if n:
		if l.right:
			n.data = l.right.data
			l.right = None
		else:
			n.data = l.left.data
			l.left = None
	return root


def deletionDeep(root, d_node):
	if root == None:
		return
	q = []
	q.append(root)
	while q:
		temp = q.pop(0)
		if temp == d_node:
			temp = None
		if temp.right:
			if temp.right == d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left == d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root == None:
		return
	if root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return root
	key_node = None
	q = []
	q.append(root)
	temp = None
	while q:
		temp = q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if key_node:
		x = temp.data
		deletionDeep(root, temp)
		key_node.data = x
	return root


def find_bottommost(root, results, level=0):
	if root is None:
		return
	if len(results) <= level:
		results.append(root.data)
	else:
		results[level] = root.data
	find_bottommost(root.left, results, level + 1)
	find_bottommost(root.right, results, level + 1)

def replace_root(root, key, target):
	if root is None:
		return root
	if root.data == target:
		root = None
		return root
	if root.data == key:
		root.data = target
	root.left = replace_root(root.left, key, target)
	root.right = replace_root(root.right, key, target)
	return root

def deletionBT(root, key):
	results = list()
	find_bottommost(root, results)
	to_replace = results[-1]
	root = replace_root(root, key, to_replace)
	return root


def deletionBT(root, key):
	if root is None:
		return
	elif root.left == None and root.right == None:
		if root.data == key:
			return
		else:
			return root
	kn = temp = last = None
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			kn = temp
		if temp.left:
			last = temp
			q.append(temp.left)
		if temp.right:
			last = temp
			q.append(temp.right)
	if kn != None:
		kn.data = temp.data
		if last.right == temp:
			last.right = None
		else:
			last.left = None
	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 inorder(root):
	if not root:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		key = int(input())
		s = input()
		root = buildTree(s)
		deletionBT(root, key)
		inorder(root)
		print()


def deletionBT(root, key):
	q = [root]
	hm = {}
	while q:
		t = q.pop(0)
		if t.left:
			q.append(t.left)
			hm[t.left] = [t, 'l']
		if t.right:
			q.append(t.right)
			hm[t.right] = [t, 'r']
		if t.data == key:
			tn = t
		if not q:
			brn = t
	tn.data = brn.data
	a = hm[brn]
	if a[1] == 'r':
		a[0].right = None
	else:
		a[0].left = None
	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 inorder(root):
	if not root:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		key = int(input())
		s = input()
		root = buildTree(s)
		deletionBT(root, key)
		inorder(root)
		print()


def deleteDeepest(root, node):
	q = [root]
	while len(q) > 0:
		temp = q.pop(0)
		if temp is node:
			temp = None
			return
		if temp.right:
			if temp.right is node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is node:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root is None:
		return
	if root.left is None and root.right is None:
		if root.data == key:
			root = None
		else:
			return root
	else:
		q = [root]
		keyNode = None
		while len(q) > 0:
			temp = q.pop(0)
			if temp.data == key:
				keyNode = temp
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
		if keyNode:
			keyNode.data = temp.data
			deleteDeepest(root, temp)
		return root


def deletionBT(root, key):
	if root is None:
		return
	ans = None
	last = None
	q = []
	q.append(root)
	while len(q) > 0:
		if q[0].data == key:
			ans = q[0]
		node = q.pop(0)
		if node.left:
			q.append(node.left)
			last = node
		if node.right:
			q.append(node.right)
			last = node
	if last.right:
		ans.data = last.right.data
		last.right = None
	else:
		ans.data = last.left.data
		last.left = None
	return root


def deleteuntil(root, temp):
	q = []
	q.append(root)
	while len(q):
		t = q.pop(0)
		if t is temp:
			t = None
			return
		if t.right:
			if t.right is temp:
				t.right = None
				return
			else:
				q.append(t.right)
		if t.left:
			if t.left is temp:
				t.left = None
				return
			else:
				q.append(t.left)

def deletionBT(root, key):
	if root is None:
		return None
	if root.left is None and root.right is None:
		if root.data == key:
			return None
		else:
			return root
	q = []
	q.append(root)
	key_node = None
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if key_node:
		x = temp.data
		deleteuntil(root, temp)
		key_node.data = x
	return root


def deletionBT(root, key):
	if root is None:
		return None
	if root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return root
	key_node = None
	array = [root]
	while len(array) > 0:
		current = array.pop(0)
		if current.data == key:
			key_node = current
		if current.left:
			array.append(current.left)
		if current.right:
			array.append(current.right)
	if key_node:
		x = current.data
		deleteDeepestNode(root, current)
		key_node.data = x
		return root

def deleteDeepestNode(root, current):
	array = [root]
	while len(array) > 0:
		curr = array.pop(0)
		if curr == current:
			curr = None
			return
		if curr.right:
			if curr.right is current:
				curr.right = None
				return
			else:
				array.append(curr.right)
		if curr.left:
			if curr.left is current:
				curr.left = None
				return
			else:
				array.append(curr.left)


def f(root, n):
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp.data == n:
			temp = None
			return
		if temp.left:
			if temp.left.data == n:
				temp.left = None
				return
			else:
				q.append(temp.left)
		if temp.right:
			if temp.right.data == n:
				temp.right = None
				return
			else:
				q.append(temp.right)

def deletionBT(root, key):
	if root is None:
		return
	else:
		q = []
		q.append(root)
		x = None
		while len(q):
			temp = q.pop(0)
			if temp.data == key:
				x = temp
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
		if x is None:
			return root
		f(root, temp.data)
		x.data = temp.data
		return 'root'


from queue import Queue

def search(root, key):
	if not root:
		return
	if root.data == key:
		return root
	lefty = search(root.left, key)
	if lefty:
		return lefty
	righty = search(root.right, key)
	if righty:
		return righty

def findlastnode(root, p, level, lcount):
	if not root:
		return (0, 0, 0, 0)
	if root and (not root.left) and (not root.right):
		lcount[0] += lcount[0]
		return (p, root, level, lcount[0] - 1)
	temp = level
	lefty = findlastnode(root.left, root, level + 1, lcount)
	righty = findlastnode(root.right, root, temp + 1, lcount)
	if lefty[2] > righty[2]:
		return lefty
	return max(lefty, righty, key=lambda x: x[3])

def deletenode(root, node):
	if node.right:
		node.right = None
		return root
	if node.left:
		node.left = None
		return root

def deletionBT(root, key):
	if root and (not root.left) and (not root.right):
		return
	level = 0
	lcount = [1]
	se = search(root, key)
	parentln = findlastnode(root, root, level, lcount)
	se.data = parentln[1].data
	deletenode(root, parentln[0])
	return


from collections import deque

def deletionBT(root, key):
	(parent, curr_parent) = (None, None)
	que = deque([root])
	while que:
		curr = que.popleft()
		if curr.data == key:
			key_node = curr
		if curr.left:
			curr_parent = curr
			que.append(curr.left)
		if curr.right:
			curr_parent = curr
			que.append(curr.right)
	if key_node:
		key_node.data = curr.data
		if curr_parent.left == curr:
			curr_parent.left = None
		elif curr_parent.right == curr:
			curr_parent.right = None
		del curr
	return root


def deletionBT(root, key):
	if root.left is None:
		if root.val == key:
			return
		else:
			return root
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if key_node:
		x = temp.data
		deld(root, temp)
		key_node.data = x
	return root

def deld(root, d_node):
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp is d_node:
			temp = None
			return
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)


def find_delete(node, key):
	if node is None:
		return None
	if node.data == key:
		return node
	left = find_delete(node.left, key)
	if left:
		return left
	return find_delete(node.right, key)

def level_order_delete(node):
	if node is None:
		return None
	q = deque()
	q.append(node)
	while q:
		node = q.popleft()
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)
	return node

def delete_right_node(root, node):
	q = deque()
	q.append(root)
	while q:
		temp = q.popleft()
		if temp.left:
			if temp.left == node:
				temp.left = None
				return
			q.append(temp.left)
		if temp.right:
			if temp.right == node:
				temp.right = None
				return
			q.append(temp.right)

def deletionBT(root, key):
	curr = find_delete(root, key)
	if curr:
		node = level_order_delete(root)
		curr.data = node.data
		delete_right_node(root, node)
	return root


from collections import deque

def deletionBT(root, key):
	q = deque()
	q.append((root, None))
	delete_node = None
	while q:
		(node, parent) = q.popleft()
		if node.data == key:
			delete_node = node
		if node.left:
			q.append((node.left, node))
		if node.right:
			q.append((node.right, node))
	delete_node.data = node.data
	if parent.right:
		parent.right = None
	else:
		parent.left = None


def deletionBT(root, key):
	if root == None:
		return None
	if root.left == None and root.right == None:
		if root.data == key:
			return None
	q = []
	q.append(root)
	temp = None
	keyNode = None
	while len(q):
		temp = q.pop(0)
		if temp.data == key:
			keyNode = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if keyNode:
		x = temp.data
		deletedeepest(root, temp)
		keyNode.data = x
	return root

def deletedeepest(root, d_node):
	temp = None
	q = []
	q.append(root)
	while q:
		temp = q.pop(0)
		if temp == d_node:
			temp = None
		if temp.left:
			if temp.left == d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)
		if temp.right:
			if temp.right == d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)


def deletionBT(root, key):
	if root is None:
		return
	if root.left == None and root.right == None:
		if root.key == key:
			return None
		else:
			return root
	q = []
	q.append(root)
	key_node = None
	while len(q) > 0:
		temp = q[0]
		q.pop(0)
		if temp.data == key:
			key_node = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if key_node is not None:
		x = temp.data
		deleteDeepest(root, temp)
		key_node.data = x
	return root

def deleteDeepest(root, key_node):
	if root is None:
		return
	q = []
	q.append(root)
	while len(q) > 0:
		temp = q[0]
		q.pop(0)
		if temp is key_node:
			temp = None
			return
		if temp.left:
			if temp.left is key_node:
				temp.left = None
				return
			else:
				q.append(temp.left)
		if temp.right:
			if temp.right is key_node:
				temp.right = None
				return
			else:
				q.append(temp.right)


def deletionBT(root, key):
	q = [root]
	node = None
	deep_node = None
	left = None
	right = None
	while q:
		deep_node = q.pop(0)
		if deep_node.data == key:
			node = deep_node
		if deep_node.left:
			q.append(deep_node.left)
			left = deep_node
			right = None
		if deep_node.right:
			q.append(deep_node.right)
			right = deep_node
			left = None
	if node:
		node.data = deep_node.data
	else:
		return -1
	if left:
		left.left = None
	if right:
		right.right = None
	return root


def deletionBT(root, key):
	(last_parent, to_del) = (None, None)
	q = [root]
	if root.data == key:
		to_del = root
	while q:
		last = q[0]
		q.pop(0)
		if last.left:
			if to_del is None and str(last.left.data) == str(key):
				to_del = last.left
			q.append(last.left)
			last_parent = last
		if last.right:
			if to_del is None and str(last.right.data) == str(key):
				to_del = last.right
			q.append(last.right)
			last_parent = last
	if last_parent and to_del:
		if last_parent.right:
			to_del.data = last_parent.right.data
			last_parent.right = None
		elif last_parent.left:
			to_del.data = last_parent.left.data
			last_parent.left = None
	return root


def deleteDepestNode(root, d_node):
	if root is None:
		return
	queue = []
	queue.append(root)
	while len(queue) > 0:
		node = queue.pop(0)
		if node == d_node:
			node = None
			return
		if node.left:
			if node.left == d_node:
				node.left = None
				return
			else:
				queue.append(node.left)
		if node.right:
			if node.right == d_node:
				node.right = None
				return
			else:
				queue.append(node.right)

def deletionBT(root, key):
	if root is None:
		return
	if root.left == None and root.right == None:
		if root.key == key:
			return None
		else:
			return root
	key_node = None
	queue = []
	queue.append(root)
	while len(queue) > 0:
		node = queue.pop(0)
		if node.data == key:
			key_node = node
		if node.left:
			queue.append(node.left)
		if node.right:
			queue.append(node.right)
	if key_node:
		depestnode_data = node.data
		deleteDepestNode(root, node)
		key_node.data = depestnode_data
	return root


def deletionBT(root, key):
	a = [root]
	node = None
	while a:
		p = a.pop(0)
		last = p
		if p.data == key:
			node = p
		if p.left:
			parent = p
			a.append(p.left)
		if p.right:
			parent = p
			a.append(p.right)
	if not node:
		return root
	if node.data != last.data:
		node.data = last.data
	if parent.right:
		parent.right = None
	else:
		parent.left = None
	return root


def deleteDeepest(root, d_node):
	q = []
	q.append(root)
	while q:
		temp = q.pop(0)
		if temp is d_node:
			temp = None
			return
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)

def deletionBT(root, key):
	if root is None:
		return
	if root is not None:
		if root.left is None and root.right is None:
			if root.data == key:
				return None
			else:
				return root
	q = []
	q.append(root)
	nnode = None
	while q:
		temp = q.pop(0)
		if temp.data == key:
			nnode = temp
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	if nnode is None:
		return root
	else:
		x = temp.data
		deleteDeepest(root, temp)
		nnode.data = x
	return root


def deletionBT(root, key):
	s = [root]
	node = None
	curr = None
	par = None
	while len(s):
		curr = s.pop(0)
		if curr.data == key:
			node = curr
		if curr.left:
			par = curr
			s.append(curr.left)
		if curr.right:
			par = curr
			s.append(curr.right)
	node.data = curr.data
	if par.right == curr:
		par.right = None
	else:
		par.left = None
	return root


def makelast_void(root, lastNode):
	if root == None:
		return None
	if root.left == lastNode:
		root.left = None
	elif root.right == lastNode:
		root.right = None
	makelast_void(root.left, lastNode)
	makelast_void(root.right, lastNode)

def deletionBT(root, key):
	if root == None:
		return None
	if root.left == None and root.right == None:
		if root.data == key:
			root = None
			return root
		return root
	q = [root]
	(lastNode, firstNode) = (None, None)
	while len(q) != 0:
		lastNode = q.pop(0)
		if lastNode.data == key:
			firstNode = lastNode
		if lastNode.left:
			q.append(lastNode.left)
		if lastNode.right:
			q.append(lastNode.right)
	if firstNode:
		firstNode.data = lastNode.data
		makelast_void(root, lastNode)
	return root


def deletionBT(root, key):
	q = [(root, -1)]
	sw = None
	node_del = None
	sw2 = None
	while q:
		(node, parent) = q.pop(0)
		if node.data == key:
			sw = node
		if node.left:
			q.append((node.left, node))
		if node.right:
			q.append((node.right, node))
	if sw:
		sw.data = node.data
		if parent.right:
			parent.right = None
		else:
			parent.left = None
	return root


def isLeaf(root):
	return root is not None and root.left is None and (root.right is None)

def findBottom(root, curr_depth, leaves):
	if root is None:
		return
	if isLeaf(root.left):
		if curr_depth in leaves:
			leaves[curr_depth].append((root.left, root, 'L'))
		else:
			leaves[curr_depth] = [(root.left, root)]
	if isLeaf(root.right):
		if curr_depth in leaves:
			leaves[curr_depth].append((root.right, root, 'R'))
		else:
			leaves[curr_depth] = [(root.right, root)]
	findBottom(root.left, curr_depth + 1, leaves)
	findBottom(root.right, curr_depth + 1, leaves)

def replace(root, key, x):
	if root is None:
		return
	if root.data == key:
		root.data = x
	replace(root.left, key, x)
	replace(root.right, key, x)

def deletionBT(root, key):
	leaves = {}
	findBottom(root, 0, leaves)
	bottomLeaves = leaves[max(leaves)]
	(leaf, parent, lr) = bottomLeaves[-1]
	if lr == 'L':
		parent.left = None
	else:
		parent.right = None
	replace(root, key, leaf.data)


def deletionBT(root, key):
	if root is None:
		return
	if root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return root
	(queue, found) = ([root], None)
	while root and len(queue):
		temp = queue.pop(0)
		if temp.data == key:
			found = temp
		if temp.left:
			queue.append(temp.left)
		if temp.right:
			queue.append(temp.right)
	if found:
		deepest_node_data = temp.data
		deletedeepest(root, temp)
		found.data = deepest_node_data
	return root

def deletedeepest(root, d_node):
	queue = [root]
	while root or len(queue):
		temp = queue.pop(0)
		if temp == d_node:
			temp = None
			return
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				queue.append(temp.left)
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				queue.append(temp.right)


def deletionBT(root, key):
	if root is None:
		return
	if root.left == None and root.right == None:
		if root.data == key:
			return None
		else:
			return root
	(queue, found) = ([root], None)
	while len(queue):
		temp = queue.pop(0)
		if temp.data == key:
			found = temp
		if temp.left:
			queue.append(temp.left)
		if temp.right:
			queue.append(temp.right)
	if found == temp:
		deletedeep(root, temp)
	if found:
		dat = temp.data
		deletedeep(root, temp)
		found.data = dat
	return root

def deletedeep(root, d_node):
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		if temp is d_node:
			temp = None
			return
		if temp.right:
			if temp.right is d_node:
				temp.right = None
				return
			else:
				q.append(temp.right)
		if temp.left:
			if temp.left is d_node:
				temp.left = None
				return
			else:
				q.append(temp.left)


def deletionBT(root, key):
	queue = [root]
	front = 0
	rear = 0
	keynode = None
	lastnode = None
	while front <= rear:
		x = rear
		while front <= x:
			if queue[front].left:
				queue.append(queue[front].left)
				rear += 1
			if queue[front].right:
				queue.append(queue[front].right)
				rear += 1
			if queue[front].data == key:
				keynode = queue[front]
			front += 1
	if keynode == None:
		return root
	lastnode = queue[rear]
	parent_lastnode = findparent(root, lastnode)
	if parent_lastnode == -1:
		return None
	keynode.data = lastnode.data
	if parent_lastnode.left == lastnode:
		parent_lastnode.left = None
	else:
		parent_lastnode.right = None
	return root

def findparent(root, node):
	queue = [root]
	front = 0
	rear = 0
	while front <= rear:
		x = rear
		while front <= x:
			if queue[front].left:
				queue.append(queue[front].left)
				rear += 1
			if queue[front].right:
				queue.append(queue[front].right)
				rear += 1
			if queue[front].left == node or queue[front].right == node:
				return queue[front]
			front += 1
	return -1


def deletionBT(root, key):
	key_ptr = None
	queue = [root]
	while queue:
		el = queue.pop(0)
		if el:
			ref_el = el
			if ref_el.data == key:
				key_ptr = ref_el
			queue.extend([ref_el.left, ref_el.right])
	key_ptr.data = ref_el.data
	ref_el.data = 'delete'
	queue = [root]
	while queue:
		el = queue.pop(0)
		if el:
			if el.left and el.left.data == ref_el.data:
				el.left = None
			elif el.right and el.right.data == ref_el.data:
				el.right = None
			queue.extend([el.left, el.right])


def deletionBT(root, key):
	q = []
	ans = []
	q.append(root)
	par = None
	while q != []:
		curr = q.pop(0)
		if curr.data == key:
			target = curr
		if curr.left != None:
			par = curr
			q.append(curr.left)
		if curr.right != None:
			par = curr
			q.append(curr.right)
	target.data = curr.data
	if par.right:
		par.right = None
	else:
		par.left = None
	return root