Given a Binary Search Tree and a node value X. Delete the node with the given value X from the BST. If no node with value x exists, then do not make any change. 
Example 1:
Input:
      2
    /   \
   1     3
X = 12
Output: 1 2 3
Explanation: In the given input there
is no node with value 12 , so the tree
will remain same.
Example 2:
Input:
            1
             \
              2
                \
                 8 
               /    \
              5      11
            /  \    /  \
           4    7  9   12
X = 9
Output: 1 2 4 5 7 8 11 12
Explanation: In the given input tree after
deleting 9 will be
             1
              \
               2
                 \
                  8
                 /   \
                5     11
               /  \     \
              4    7     12
Your Task:
You don't need to read input or print anything. Your task is to complete the function deleteNode() which takes two arguments. The first being the root of the tree, and an integer 'X' denoting the node value to be deleted from the BST. Return the root of the BST after deleting the node with value X. Do not make any update if there's no node with value X present in the BST. 
Note: The generated output will be the inorder traversal of the modified tree.
 
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3





#Function to delete a node from BST.

def deleteNode(root, X):

    # code here.

Solutions:
def deleteNode(root, X):
	if not root:
		return None
	if X < root.data:
		root.left = deleteNode(root.left, X)
	elif X > root.data:
		root.right = deleteNode(root.right, X)
	else:
		if root.left is None and root.right is None:
			return None
		elif not root.left:
			current = root.right
			root = None
			return current
		elif not root.right:
			current = root.left
			root = None
			return current
		succParent = root
		succ = root.right
		while succ.left != None:
			succParent = succ
			succ = succ.left
		if succParent != root:
			succParent.left = succ.right
		else:
			succParent.right = succ.right
		root.data = succ.data
	return root


def getSucc(curr, key):
	while curr.left != None:
		curr = curr.left
	return curr.data

def deleteNode(root, X):
	if root == None:
		return
	if root.data > X:
		root.left = deleteNode(root.left, X)
	if root.data < X:
		root.right = deleteNode(root.right, X)
	if root.data == X:
		if root.left == None:
			return root.right
		elif root.right == None:
			return root.left
		else:
			succ = getSucc(root.right, X)
			root.data = succ
			root.right = deleteNode(root.right, succ)
	return root


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

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


def sol(curr):
	while curr.left != None:
		curr = curr.left
	return curr.data

def deleteNode(root, X):
	if root == None:
		return root
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	else:
		if root.left == None and root.right == None:
			return None
		if root.left == None:
			return root.right
		elif root.right == None:
			return root.left
		else:
			nextsucc = sol(root.right)
			root.data = nextsucc
			root.right = deleteNode(root.right, nextsucc)
		return root
	return root


class Node:

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

def insert(root, key):
	if root is None:
		return Node(key)
	if key < root.data:
		root.left = insert(root.left, key)
	else:
		root.right = insert(root.right, key)
	return root

def inorder(root):
	if root is not None:
		inorder(root.left)
		print(root.data, end=' ')
		inorder(root.right)

def mini(root):
	if root is None:
		return None
	while root.left is not None:
		root = root.left
	return root.data

def deleteNode(root, X):
	if root is None:
		return None
	if root.data == X:
		if root.left is None:
			return root.right
		elif root.right is None:
			return root.left
		else:
			root.data = mini(root.right)
			root.right = deleteNode(root.right, root.data)
		return root
	if root.data > X:
		root.left = deleteNode(root.left, X)
	else:
		root.right = deleteNode(root.right, X)
	return root


def deleteNode(root, X):

	def minimum(root):
		if root.left is None:
			return root.data
		return minimum(root.left)

	def deleteHelper(root, data):
		if not root:
			return (False, None)
		if root.data < data:
			(deleted, newRightNode) = deleteHelper(root.right, data)
			root.right = newRightNode
			return (deleted, root)
		if root.data > data:
			(deleted, newLeftNode) = deleteHelper(root.left, data)
			root.left = newLeftNode
			return (deleted, root)
		if not root.left and (not root.right):
			return (True, None)
		if root.left == None:
			return (True, root.right)
		if root.right == None:
			return (True, root.left)
		replacement = minimum(root.right)
		root.data = replacement
		(deleted, newRightNode) = deleteHelper(root.right, replacement)
		root.right = newRightNode
		return (True, root)

	def deleteData(root, x):
		(deleted, newRoot) = deleteHelper(root, x)
		if not deleted:
			return root
		return newRoot
	return deleteData(root, x)


def mini(root):
	while root.left != None:
		root = root.left
	return root.data

def deleteNode(root, X):
	if root == None:
		return None
	if root.data > X:
		root.left = deleteNode(root.left, X)
	if root.data < X:
		root.right = deleteNode(root.right, X)
	if root.data == X:
		if root.left == None and root.right == None:
			return None
		if root.left != None and root.right == None:
			return root.left
		if root.right != None and root.left == None:
			return root.right
		if root.left != None and root.right != None:
			root.data = mini(root.right)
			root.right = deleteNode(root.right, root.data)
	return root


def deleteNode(root, X):
	if root == None:
		return root
	if root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.left == None and root.right == None:
		return None
	elif root.left != None and root.right == None:
		return root.left
	elif root.left == None and root.right != None:
		return root.right
	else:
		root.data = min(root.right)
		root.right = deleteNode(root.right, root.data)
	return root

def min(root):
	curr = root
	while curr.left != None:
		curr = curr.left
	return curr.data


class Node:

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

def getsucc(curr, key):
	succ = None
	while curr:
		if curr.data > key:
			succ = curr
			curr = curr.left
		else:
			curr = curr.right
	return succ.data if succ else None

def deleteNode(root, X):
	if root == None:
		return
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		succ = getsucc(root.right, X)
		root.data = succ
		root.right = deleteNode(root.right, succ)
	return root


def getsucc(root):
	cur = root.right
	while cur.left:
		cur = cur.left
	return cur

def deleteNode(root, key):
	if root == None:
		return None
	if key < root.data:
		root.left = deleteNode(root.left, key)
	elif key > root.data:
		root.right = deleteNode(root.right, key)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		succ = getsucc(root)
		root.data = succ.data
		root.right = deleteNode(root.right, succ.data)
	return root


def deleteNode(node, X):
	root = __delete(node, X)
	return root

def __delete(node, X):
	if not node:
		return
	elif node.data > X:
		node.left = __delete(node.left, X)
	elif node.data < X:
		node.right = __delete(node.right, X)
	elif not node.left:
		return node.right
	elif not node.right:
		return node.left
	else:
		succ = minNode(node.right)
		node.data = succ
		node.right = __delete(node.right, succ)
	return node

def minNode(node):
	while node and node.left:
		node = node.left
	return node.data


def successor(root):
	while root.left:
		root = root.left
	return root.data

def deleteNode(root, X):
	if root is None:
		return None
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left is None:
		return root.right
	elif root.right is None:
		return root.left
	else:
		succ = successor(root.right)
		root.data = succ
		root.right = deleteNode(root.right, succ)
	return root


def mini(root):
	if not root:
		return None
	while root.left != None:
		root = root.left
	return root.data

def deleteNode(root, X):
	if not root:
		return None
	if root.data == X:
		if root.left == None and root.right == None:
			return None
		if root.left != None and root.right == None:
			return root.left
		if root.left == None and root.right != None:
			return root.right
		else:
			root.data = mini(root.right)
			root.right = deleteNode(root.right, root.data)
	elif root.data > X:
		root.left = deleteNode(root.left, X)
	else:
		root.right = deleteNode(root.right, X)
	return root


def deleteNode(root, X):
	if root is None:
		return root
	if X > root.data:
		root.right = deleteNode(root.right, X)
	elif X < root.data:
		root.left = deleteNode(root.left, X)
	else:
		if root.left is None:
			temp = root.right
			return temp
		if root.right is None:
			temp = root.left
			return temp
		else:
			succ = findInorderSuccessor(root)
			root.data = succ.data
			root.right = deleteNode(root.right, succ.data)
	return root

def findInorderSuccessor(curr):
	curr = curr.right
	while curr and curr.left:
		curr = curr.left
	return curr


def nextlargest(root):
	if root.left is None:
		return root.data
	return nextlargest(root.left)

def delnode(root):
	if root.left is None:
		return root.right
	if root.right is None:
		return root.left
	root.data = nextlargest(root.right)
	root.right = deleteNode(root.right, root.data)
	return root

def deleteNode(root, X):
	if root is None:
		return root
	if root.data == X:
		return delnode(root)
	if root.data < X:
		root.right = deleteNode(root.right, X)
	else:
		root.left = deleteNode(root.left, X)
	return root


def deleteNode(root, key):
	if not root:
		return None

	def minimum(r):
		curr = r
		while curr.left:
			curr = curr.left
		return curr
	if key < root.data:
		root.left = deleteNode(root.left, key)
	elif key > root.data:
		root.right = deleteNode(root.right, key)
	else:
		if not root.right:
			temp = root.left
			return temp
		if not root.left:
			temp = root.right
			return temp
		min_node = minimum(root.right)
		root.data = min_node.data
		root.right = deleteNode(root.right, min_node.data)
	return root


def deleteNode(root, X):
	if root == None:
		return None
	if root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.data > X:
		root.left = deleteNode(root.left, X)
	else:
		if root.left == None:
			return root.right
		if root.right == None:
			return root.left
		if root.right and root.left:
			temp = root.right
			while temp.left:
				temp = temp.left
			root.data = temp.data
			root.right = deleteNode(root.right, temp.data)
	return root


def deleteNode(root, key):

	def findRightToConnect(root):
		if root.right == None:
			return root
		return findRightToConnect(root.right)

	def helper(root):
		if root.left == None and root.right == None:
			return None
		if root.left == None:
			return root.right
		if root.right == None:
			return root.left
		rightChild = root.right
		leftChild = findRightToConnect(root.left)
		leftChild.right = rightChild
		return root.left

	def deleteBST(root, key):
		if key == root.data:
			return helper(root)
		cur = root
		while root:
			if key > root.data:
				if root.right and root.right.data == key:
					root.right = helper(root.right)
					break
				else:
					root = root.right
			elif root.left and root.left.data == key:
				root.left = helper(root.left)
			else:
				root = root.left
		return cur
	return deleteBST(root, key)


def deleteNode(root, key):

	def findlastroot(root):
		if root.right == None:
			return root
		return findlastroot(root.right)

	def helper(root):
		if root.left == None and root.right == None:
			return None
		if root.left == None:
			return root.right
		if root.right == None:
			return root.left
		rc = root.right
		lc = findlastroot(root.left)
		lc.right = rc
		return root.left

	def deleteBST(root, key):
		if root == None:
			return None
		if root.data == key:
			return helper(root)
		curr = root
		while root != None:
			if root.data > key:
				if root.left != None and root.left.data == key:
					root.left = helper(root.left)
					break
				else:
					root = root.left
			elif root.right != None and root.right.data == key:
				root.right = helper(root.right)
				break
			else:
				root = root.right
		return curr
	return deleteBST(root, key)


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

def deleteNode(root, X):
	if root == None:
		return root
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	else:
		if root.left == None:
			temp = root.right
			root = None
			return temp
		if root.right == None:
			temp = root.left
			root = None
			return temp
		temp = min_value(root.right)
		root.data = temp.data
		root.right = deleteNode(root.right, temp.data)
	return root


def deleteNode(root, X):

	def succroot(curr, X):
		while curr.left != None:
			curr = curr.left
		return curr.data
	if root == None:
		return
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		succ = succroot(root.right, X)
		root.data = succ
		root.right = deleteNode(root.right, succ)
	return root


def getx(curr, c):
	while curr.left != None:
		curr = curr.left
	return curr.data

def deleteNode(root, X):
	if root == None:
		return
	elif root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		succ = getx(root.right, X)
		root.data = succ
		root.right = deleteNode(root.right, succ)
	return root


def deleteNode(root, X):

	def minValue(root):
		minValue = root.data
		while root.left != None:
			minValue = root.left.data
			root = root.left
		return minValue
	if root == None:
		return
	if X < root.data:
		root.left = deleteNode(root.left, X)
	elif X > root.data:
		root.right = deleteNode(root.right, X)
	else:
		if root.left == None:
			return root.right
		if root.right == None:
			return root.left
		root.data = minValue(root.right)
		root.right = deleteNode(root.right, root.data)
	return root


def minValue(root):
	if root is None:
		return None
	while root.left is not None:
		root = root.left
	return root.data

def deleteNode(root, X):
	if root is None:
		return None
	if X == root.data:
		if root.left is None:
			return root.right
		if root.right is None:
			return root.left
		else:
			root.data = minValue(root.right)
			root.right = deleteNode(root.right, root.data)
	if X > root.data:
		root.right = deleteNode(root.right, X)
	else:
		root.left = deleteNode(root.left, X)
	return root


def deleteNode(root, X):
	node = root
	found = False
	parent = None
	side = 0
	while node:
		parent = node
		if node.data == X:
			found = True
			break
		elif node.data < X:
			node = node.left
			side = -1
		elif node.data > X:
			node = node.right
			side = 1
	if not found:
		return root
	if node.left and node.right:
		successor = node.right
		parent = node
		while successor.left:
			parent = successor
			successor = successor.left
		if node is parent:
			parent.right = successor.right
		else:
			parent.left = successor.right
		node.data = successor.data
	elif node.left:
		if side == 1:
			parent.right = node.left
		elif side == -1:
			parent.left = node.left
		elif side == 0:
			return node.left
	elif node.right:
		if side == 1:
			parent.right = node.right
		elif side == -1:
			parent.left = node.right
		elif side == 0:
			return node.right
	elif side == 1:
		parent.right = None
	elif side == -1:
		parent.left = None
	elif side == 0:
		return None
	return root


def found_node(root, X, pre):
	if root == None:
		return -1
	if root.data > X:
		pre[0] = root
		return found_node(root.left, X, pre)
	elif root.data < X:
		pre[0] = root
		return found_node(root.right, X, pre)
	else:
		return root

def getInorderPre(curr):
	prev = None
	curr = curr.left
	while curr.right:
		prev = curr
		curr = curr.right
	return (curr, prev)

def delete_node(curr, X, pre):
	if curr.left == None and curr.right == None:
		if pre[0].left == curr:
			pre[0].left = None
		else:
			pre[0].right = None
	elif curr.left == None:
		if pre[0].left == curr:
			pre[0].left = curr.right
		else:
			pre[0].right = curr.right
	elif curr.right == None:
		if pre[0].right == curr:
			pre[0].right = curr.left
		else:
			pre[0].left = curr.left
	else:
		(greatestLT, prev) = getInorderPre(curr)
		curr.data = greatestLT.data
		if prev == None:
			curr.left = greatestLT.left
		elif prev.left == greatestLT:
			prev.left = greatestLT.left
		else:
			prev.right = greatestLT.left
		return

def deleteNode(root, X):
	if root == None:
		return root
	elif root.data == X:
		if root.left == None and root.right == None:
			return None
		elif root.left == None:
			deleted = root
			root = root.right
			deleted.right = None
			return root
		elif root.right == None:
			deleted = root
			root = root.left
			deleted.left = None
			return root
		else:
			(greatestLT, prev) = getInorderPre(root)
			root.data = greatestLT.data
			if prev == None:
				root.left = greatestLT.left
			elif prev.left == greatestLT:
				prev.left = greatestLT.left
			else:
				prev.right = greatestLT.left
			return root
	else:
		pre = [None]
		curr = found_node(root, X, pre)
		if curr != -1:
			delete_node(curr, X, pre)
		return root


def deleteNode(root, x):
	if not root:
		return
	if root.data > x:
		root.left = deleteNode(root.left, x)
	elif root.data < x:
		root.right = deleteNode(root.right, x)
	elif not root.left:
		return root.right
	elif not root.right:
		return root.left
	else:
		node = root.right
		while node.left:
			node = node.left
		root.data = node.data
		root.right = deleteNode(root.right, node.data)
	return root


def deleteNode(root, X):
	if not root:
		return None
	if root.data == X:
		if not root.left and (not root.right):
			return None
		if root.left and (not root.right):
			return root.left
		if not root.left and root.right:
			return root.right
		ptr = root.right
		while ptr.left:
			ptr = ptr.left
		root.data = ptr.data
		root.right = deleteNode(root.right, root.data)
	if root.data > X:
		root.left = deleteNode(root.left, X)
	if root.data < X:
		root.right = deleteNode(root.right, X)
	return root


def deleteNode(root, x):
	if root == None:
		return None
	if root.data == x:
		if root.left == None and root.right == None:
			return None
		if root.left == None and root.right is not None:
			return root.right
		if root.left is not None and root.right == None:
			return root.left
		else:
			root.data = smallest(root.right)
			root.right = deleteNode(root.right, root.data)
	elif root.data > x:
		root.left = deleteNode(root.left, x)
	else:
		root.right = deleteNode(root.right, x)
	return root

def smallest(root):
	if root == None:
		return None
	while root.left:
		root = root.left
	return root.data


def deleteNode(root, X):
	if root is None:
		return root
	if X < root.data:
		root.left = deleteNode(root.left, X)
	elif X > root.data:
		root.right = deleteNode(root.right, X)
	elif root.left is None and root.right is None:
		return None
	elif root.left is None:
		return root.right
	elif root.right is None:
		return root.left
	else:
		successor = minimumNode(root.right)
		root.data = successor.data
		root.right = deleteNode(root.right, successor.data)
	return root

def minimumNode(node):
	while node.left:
		node = node.left
	return node


def findMaximum(root):
	cur = root
	while cur.right:
		cur = cur.right
	return cur

def deleteNode(root, x):
	if root == None:
		return root
	if x < root.data:
		root.left = deleteNode(root.left, x)
	elif x > root.data:
		root.right = deleteNode(root.right, x)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		temp = findMaximum(root.left)
		root.data = temp.data
		root.left = deleteNode(root.left, temp.data)
	return root


def mv(node):
	c = node
	while c.left != None:
		c = c.left
	return c

def deleteNode(root, X):
	if not root:
		return root
	elif X < root.data:
		root.left = deleteNode(root.left, X)
	elif X > root.data:
		root.right = deleteNode(root.right, X)
	else:
		if not root.right:
			temp = root.left
			root = None
			return temp
		if not root.left:
			temp = root.right
			root = None
			return temp
		temp = mv(root.right)
		root.data = temp.data
		root.right = deleteNode(root.right, temp.data)
	return root


def ll(node):
	while node.right:
		node = node.right
	return node

def find(curr):
	if curr.left is None:
		return curr.right
	elif curr.right is None:
		return curr.left
	else:
		left_sub = curr.left
		right_sub = curr.right
		x = ll(left_sub)
		x.right = right_sub
		return left_sub

def deleteNode(root, x):
	curr = root
	if root.data == x:
		return find(root)
	if root is None:
		return root
	while curr:
		if x > curr.data:
			if curr.right and x == curr.right:
				curr.right = find(curr)
			else:
				curr = curr.right
		elif x < curr.data:
			if curr.left and x == curr.left:
				curr.left = find(curr)
			else:
				curr = curr.left
	return root


def minimum(root):
	if root == None:
		return None
	while root.left != None:
		root = root.left
	return root.data

def deleteNode(root, X):
	if root == None:
		return None
	if root.data == X:
		if root.left == None and root.right == None:
			return None
		if root.left != None and root.right == None:
			return root.left
		if root.right != None and root.left == None:
			root.right
		else:
			root.data = minimum(root.right)
			root.right = deleteNode(root.right, root.data)
	if root.data > X:
		root.left = deleteNode(root.left, X)
	else:
		root.right = deleteNode(root.right, X)
	return root


def minvalueNode(root):
	while root.left:
		root = root.left
	return root

def deleteNode(root, x):
	if root is None:
		return
	if x < root.data:
		root.left = deleteNode(root.left, x)
	elif x > root.data:
		root.right = deleteNode(root.right, x)
	else:
		if root.left is None:
			return root.right
		if root.right is None:
			return root.left
		node = minvalueNode(root.right)
		root.data = node.data
		root.right = deleteNode(root.right, node.data)
	return root


def get(root):
	cu = root.right
	while cu is not None and cu.left is not None:
		cu = cu.left
	return cu

def deleteNode(root, X):
	if root is None:
		return None
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left is None:
		return root.right
	elif root.right is None:
		return root.left
	else:
		su = get(root)
		root.data = su.data
		root.right = deleteNode(root.right, su.data)
	return root


def fun(curr):
	while curr.left != None:
		curr = curr.left
	return curr.data

def deleteNode(root, X):
	if root == None:
		return
	if root.data > X:
		root.left = deleteNode(root.left, X)
	elif root.data < X:
		root.right = deleteNode(root.right, X)
	elif root.left == None:
		return root.right
	elif root.right == None:
		return root.left
	else:
		key = fun(root.right)
		root.data = key
		root.right = deleteNode(root.right, key)
	return root


def find_l(root, prev):
	cur = root
	if cur.right == None:
		c = cur.data
		prev.left = cur.left
		return c
	while cur.right != None:
		prev = cur
		cur = cur.right
	c = cur.data
	prev.right = cur.left
	return c

def deleteNode(root, X):
	prev = None
	if root.data == X:
		if root.left == None and root.right == None:
			return prev

	def d_n(root, X):
		if root:
			cur = root
			if root.data == X:
				if root.left:
					r = find_l(root.left, root)
					root.data = r
					return root
				if root.right:
					k = root.right
					if prev == None and k.left == None and (k.right == None):
						return k
					prev.left = cur.right
					return root
				if root.left == None and root.right == None:
					if prev.left.data == X:
						prev.left = None
						return root
					if prev.right.data == X:
						prev.right = None
						return root
			prev = cur
			d_n(root.left, X)
			d_n(root.right, X)
		return root
	d = d_n(root, X)
	return d


def minval(root):
	curr = root
	while curr.left:
		curr = curr.left
	return curr

def deleteNode(root, key):
	if root == None:
		return None
	if key < root.data:
		root.left = deleteNode(root.left, key)
		return root
	elif key > root.data:
		root.right = deleteNode(root.right, key)
		return root
	elif root.left == None and root.right == None:
		return None
	elif root.left and (not root.right):
		temp = root.left
		root = None
		return temp
	elif root.right and (not root.left):
		temp = root.right
		root = None
		return temp
	else:
		temp = minval(root.right)
		root.data = temp.data
		root.right = deleteNode(root.right, temp.data)
		return root