There is BST given with the root node with the key part as an integer only. You need to find the in-order successor and predecessor of a given key. If either predecessor or successor is not found, then set it to NULL.
Note:- In an inorder traversal the number just smaller than the target is the predecessor and the number just greater than the target is the successor. 
Example 1:
Input:
        10
      /   \
     2    11
   /  \ 
  1    5
      /  \
     3    6
      \
       4
key = 8
Output: 
6 10
Explanation: 
In the given BST the inorder predecessor of 8 is 6 and inorder successor of 8 is 10.
Example 2:
Input:
      8
    /   \
   1     9
    \     \
     4    10
    /
   3
key = 11
Output: 
10 -1
Explanation: 
In given BST, the inorder predecessor of 11 is 10 whereas it does not have any inorder successor.
Your Task: You don't need to print anything. You need to update pre with the predecessor of the key or NULL if the predecessor doesn't exist and succ to the successor of the key or NULL if the successor doesn't exist. pre and succ are passed as an argument to the function findPreSuc(). 
Expected Time Complexity: O(Height of the BST).Expected Auxiliary Space: O(Height of the BST).
Constraints: 
1 <= Number of nodes <= 10^{4}
1 <= key of node <= 10^{7}
1 <= key <= 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: '''

class Node:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

'''





# This function finds predecessor and successor of key in BST.

# It sets pre and suc as predecessor and successor respectively

class Solution:

    def findPreSuc(self, root, pre, suc, key):

        # Your code goes here

Solutions:
def findPreSuc(root, pre, suc, key):
	stack = []
	prev = None
	while True:
		if root:
			stack.append(root)
			root = root.left
		else:
			if not stack:
				break
			root = stack.pop()
			if root.key > key:
				break
			else:
				if root.key != key:
					prev = root
				root = root.right
	pre[0] = prev
	suc[0] = root


def findPreSuc(root, pre, suc, key):
	pre[0] = None
	suc[0] = None

	def succ(root, key):
		if root is None:
			return
		if root.key > key:
			nonlocal suc
			suc[0] = root
			succ(root.left, key)
		else:
			succ(root.right, key)

	def pred(root, key):
		if root is None:
			return
		if root.key < key:
			nonlocal pre
			pre[0] = root
			pred(root.right, key)
		else:
			pred(root.left, key)
	pred(root, key)
	succ(root, key)


def findPreSuc(root, pre, suc, key):
	node = root
	while node != None:
		if key <= node.key:
			node = node.left
		else:
			pre[0] = node
			node = node.right
	while root != None:
		if key >= root.key:
			root = root.right
		else:
			suc[0] = root
			root = root.left


def findPreSuc(root, pre, suc, key):
	if root == None:
		return
	findPreSuc(root.left, pre, suc, key)
	if root.key < key:
		pre[0] = root
	if root.key > key:
		if suc[0] == None or root.key < suc[0].key:
			suc[0] = root
	findPreSuc(root.right, pre, suc, key)


def findPreSuc(root, pre, suc, key):
	if root is None:
		return
	elif root.key == key:
		if root.left:
			pre[0] = root.left
			findPreSuc(root.left.right, pre, suc, key)
		if root.right:
			suc[0] = root.right
			findPreSuc(root.right.left, pre, suc, key)
	elif root.key < key:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)
	elif root.key > key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)


def findPreSuc(root, pre, suc, key):
	c = root
	while c:
		if c.key < key:
			pre[0] = c
			c = c.right
		else:
			c = c.left
	c = root
	while c:
		if c.key > key:
			suc[0] = c
			c = c.left
		else:
			c = c.right


def findPreSuc(root, pre, suc, key):
	lol.pre = None
	lol.suc = None
	lol(root, key)
	pre[0] = lol.pre
	suc[0] = lol.suc

def lol(root, key):
	if root is None:
		return
	if root.key == key:
		if root.left is not None:
			tmp = root.left
			while tmp.right:
				tmp = tmp.right
			lol.pre = tmp
		if root.right is not None:
			tmp = root.right
			while tmp.left:
				tmp = tmp.left
			lol.suc = tmp
		return
	if root.key > key:
		lol.suc = root
		lol(root.left, key)
	else:
		lol.pre = root
		lol(root.right, key)


def findPreSuc(root, pre, suc, key):

	def succ(root, suc):
		while root != None:
			if root.key <= key:
				root = root.right
			else:
				suc[0] = root
				root = root.left

	def pres(root, pre):
		while root != None:
			if root.key >= key:
				root = root.left
			else:
				pre[0] = root
				root = root.right
	succ(root, suc)
	pres(root, pre)


def findPreSuc(root, pre, suc, key):
	if not root:
		return
	if root.key == key:
		if root.left:
			tmp = root.left
			while tmp.right:
				tmp = tmp.right
			pre[0] = tmp
		if root.right:
			tmp = root.right
			while tmp.left:
				tmp = tmp.left
			suc[0] = tmp
		return
	if root.key > key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	else:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)


def floor(node, key):
	res = None
	while node:
		if node.key >= key:
			node = node.left
		else:
			res = node
			node = node.right
	return res

def ceil(node, key):
	res = None
	while node:
		if node.key > key:
			res = node
			node = node.left
		else:
			node = node.right
	return res

def findPreSuc(root, pre, suc, key):
	pre[0] = floor(root, key)
	suc[0] = ceil(root, key)


def findPreSuc(root, pre, suc, key):
	curr = root
	next = root
	while curr is not None:
		if curr.key <= key:
			curr = curr.right
		else:
			suc[0] = curr
			curr = curr.left
	while root is not None:
		if root.key >= key:
			root = root.left
		else:
			pre[0] = root
			root = root.right
	return


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

def findPreSuc(root, pre, suc, data):
	kl = inorder(root)
	pre[0] = None
	suc[0] = None
	for i in range(len(kl)):
		if kl[i].key == data:
			if i - 1 >= 0:
				pre[0] = kl[i - 1]
			if i + 1 < len(kl):
				suc[0] = kl[i + 1]
			return (pre, suc)
		elif kl[i].key > data:
			if i - 1 >= 0:
				pre[0] = kl[i - 1]
			suc[0] = kl[i]
			return (pre, suc)
	if kl[len(kl) - 1].key < data:
		pre[0] = kl[len(kl) - 1]
		suc[0] = None
	return (pre, suc)


def findPreSuc(root, pre, suc, key):
	ans = []

	def binarySearch(ans, key):
		low = 0
		high = len(ans)
		while low < high:
			mid = (low + high) // 2
			if ans[mid] == key:
				return mid
			elif ans[mid] > key:
				high = mid
			else:
				low = mid + 1
		return low

	def inorder(root, d):
		if root is None:
			return
		inorder(root.left, d)
		ans.append(root.key)
		d[root.key] = root
		inorder(root.right, d)
	d = {}
	inorder(root, d)
	res = []
	ind = binarySearch(ans, key)
	if ind < len(ans) and ans[ind] == key:
		if ind - 1 >= 0:
			pre[0] = d[ans[ind - 1]]
		if ind + 1 < len(ans):
			suc[0] = d[ans[ind + 1]]
	else:
		if ind - 1 >= 0:
			pre[0] = d[ans[ind - 1]]
		if ind < len(ans):
			suc[0] = d[ans[ind]]


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

def findPreSuc(root, pre, suc, k):
	arr = []
	inorder(root, arr)
	mini = 99999
	maxi = -1
	for i in arr:
		if i.key < k:
			mini = i
		else:
			break
	for i in range(len(arr) - 1, -1, -1):
		if arr[i].key > k:
			maxi = arr[i]
		else:
			break
	if mini != 99999:
		pre[0] = mini
	if maxi != -1:
		suc[0] = maxi


def findPreSuc(root, pre, suc, key):

	def findSuc(root):
		while root != None:
			if key >= root.key:
				root = root.right
			else:
				suc[0] = root
				root = root.left

	def findPre(root):
		while root != None:
			if key <= root.key:
				root = root.left
			else:
				pre[0] = root
				root = root.right
	findPre(root)
	findSuc(root)


def findPreSuc(root, pre, suc, key):
	if root is None:
		return
	findPreSuc(root.left, pre, suc, key)
	findPreSuc(root.right, pre, suc, key)
	if root.key > key and (suc[0] is None or suc[0].key > root.key):
		suc[0] = root
	if root.key < key and (pre[0] is None or pre[0].key < root.key):
		pre[0] = root

def findNode(root, key):
	if root is None:
		return
	if root.key > key:
		return findNode(root.left, key)
	elif root.key < key:
		return findNode(root.right, key)
	else:
		return root


def findPreSuc(root, pre, suc, key):
	if root is None:
		return
	if root.key == key:
		if root.left:
			temp = root.left
			while temp.right:
				temp = temp.right
			pre[0] = temp
		if root.right:
			temp = root.right
			while temp.left:
				temp = temp.left
			suc[0] = temp
		return
	if root.key > key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	else:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)
	return


def findPreSuc(root, pre, suc, key):
	mn = 0
	mnD = 1000
	mx = 0
	mxD = 1000
	temp = root
	while temp:
		if temp.key < key and key - temp.key < mnD:
			mnD = key - temp.key
			mn = temp.key
		if temp.key >= key:
			temp = temp.left
		else:
			temp = temp.right
	temp = root
	while temp:
		if temp.key > key and abs(key - temp.key) < mxD:
			mxD = abs(key - temp.key)
			mx = temp.key
		if temp.key > key:
			temp = temp.left
		else:
			temp = temp.right
	if mxD == 1000:
		mx = -1
	if mnD == 1000:
		mn = -1
	pre[0] = Node(mn)
	suc[0] = Node(mx)


def findPreSuc(root, pre, suc, key):

	def search(root, key):
		if root is None:
			return
		if root.key == key:
			if root.left:
				t = root.left
				while t.right:
					t = t.right
				pre[0] = t
			if root.right:
				t = root.right
				while t.left:
					t = t.left
				suc[0] = t
		elif root.key < key:
			pre[0] = root
			search(root.right, key)
		else:
			suc[0] = root
			search(root.left, key)
	search(root, key)


def inorder(root):
	if not root:
		return []
	d = []
	d += inorder(root.left)
	d.append(root.key)
	d += inorder(root.right)
	return d
	inorder(root.right, pre, suc, key)

def findPreSuc(root, pre, suc, key):
	d = inorder(root)
	for i in d:
		if i < key:
			pre[0] = Node(i)
		if i > key:
			suc[0] = Node(i)
			break


def findPreSuc(root, pre, suc, key):
	if not root:
		return
	if key < root.key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	elif key > root.key:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)
	else:
		findPreSuc(root.left, pre, suc, key)
		findPreSuc(root.right, pre, suc, key)
	return


def findPreSuc(root, pre, suc, key):

	def findsuc(root):
		if not root:
			return
		if root.key > key:
			suc[0] = root
			findsuc(root.left)
		else:
			findsuc(root.right)
		return

	def findspre(root):
		if not root:
			return
		if root.key < key:
			pre[0] = root
			findspre(root.right)
		else:
			findspre(root.left)
		return
	findsuc(root)
	findspre(root)


def inPre(node):
	prenode = node.left
	while prenode.right:
		prenode = prenode.right
	return prenode

def inSuc(node):
	sucnode = node.right
	while sucnode.left:
		sucnode = sucnode.left
	return sucnode

def findPreSuc(root, pre, suc, key):
	if root == None:
		return
	if root.key == key:
		if root.left:
			pre[0] = inPre(root)
		if root.right:
			suc[0] = inSuc(root)
		return
	if root.key > key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	elif root.key < key:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)


def findPreSuc(root, pre, suc, key):
	cur = root
	while cur:
		if cur.key > key:
			suc[0] = cur
			cur = cur.left
		else:
			cur = cur.right
	cur = root
	while cur:
		if cur.key < key:
			pre[0] = cur
			cur = cur.right
		else:
			cur = cur.left
	return [pre[0], suc[0]]


def solve(root, mini, maxa, key):
	if root == None:
		return
	if root.key < key and root.key > mini[0]:
		mini[0] = root.key
	if root.key > key and root.key < maxa[0]:
		maxa[0] = root.key
	solve(root.left, mini, maxa, key)
	solve(root.right, mini, maxa, key)

def findPreSuc(root, pre, suc, key):
	mini = [-1000000]
	maxa = [1000000]
	solve(root, mini, maxa, key)
	if mini[0] != -1000000:
		pre[0] = Node(mini[0])
	if maxa[0] != 1000000:
		suc[0] = Node(maxa[0])
	return (pre, suc)


def findPreSuc(root, pre, suc, key):
	inr2 = []
	inr = []

	def inorder(node):
		if not node:
			return
		inorder(node.left)
		inr.append(node)
		inr2.append(node.key)
		inorder(node.right)
	inorder(root)
	pre[0] = None
	suc[0] = None
	n = len(inr)
	for i in range(n):
		if inr2[i] > key:
			suc[0] = inr[i]
			break
	for j in range(n - 1, -1, -1):
		if inr2[j] < key:
			pre[0] = inr[j]
			break


def findPreSuc(root, pre, suc, key):
	temp = root
	while temp:
		if key < temp.key:
			suc[0] = temp
			temp = temp.left
		elif key > temp.key:
			pre[0] = temp
			temp = temp.right
		else:
			if temp.left:
				pre[0] = temp.left
				while pre[0].right:
					pre[0] = pre[0].right
			if temp.right:
				suc[0] = temp.right
				while suc[0].left:
					suc[0] = suc[0].left
			break


def pred(root):
	root = root.left
	while root.right:
		root = root.right
	return root

def succ(root):
	root = root.right
	while root.left:
		root = root.left
	return root

def findPreSuc(root, pre, suc, key):
	if not root:
		return
	if root.key == key:
		if root.left:
			pre[0] = pred(root)
		if root.right:
			suc[0] = succ(root)
	if key < root.key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	if key > root.key:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)


def findPreSuc(root, pre, suc, key):

	def successor(root, pre, suc, key):
		while root:
			if key >= root.key:
				root = root.right
			else:
				suc[0] = root
				root = root.left
		return suc

	def predecessor(root, pre, suc, key):
		while root:
			if key > root.key:
				pre[0] = root
				root = root.right
			else:
				root = root.left
		return pre
	suc = successor(root, pre, suc, key)
	pre = predecessor(root, pre, suc, key)
	return (pre, suc)


def findPreSuc(root, pre, suc, key):
	if root != None:
		findPreSuc(root.left, pre, suc, key)
		if root.key < key:
			pre[0] = root
		if root.key > key:
			if suc[0] == None:
				suc[0] = root
		findPreSuc(root.right, pre, suc, key)


def InOrder(root, lis):
	if root != None:
		InOrder(root.left, lis)
		lis.append(root)
		InOrder(root.right, lis)

def findPreSuc(root, pre, suc, key):
	lis = []
	InOrder(root, lis)
	for i in range(0, len(lis)):
		if lis[i].key == key:
			if i - 1 >= 0:
				pre[0] = lis[i - 1]
			if i + 1 < len(lis):
				suc[0] = lis[i + 1]
			break
		if lis[i].key < key and i + 1 < len(lis) and (lis[i + 1].key > key):
			pre[0] = lis[i]
			suc[0] = lis[i + 1]
			break
		if lis[i].key < key and i + 1 == len(lis):
			pre[0] = lis[i]
			break


def findPreSuc(root, pre, suc, key):
	pre[0] = suc[0] = Node(-1)
	dummy = root
	while dummy is not None:
		if dummy.key < key:
			pre[0] = dummy
			dummy = dummy.right
		else:
			dummy = dummy.left
	dummy = root
	while dummy is not None:
		if dummy.key > key:
			suc[0] = dummy
			dummy = dummy.left
		else:
			dummy = dummy.right


def findPreSuc(root, pre, suc, data):

	def find(root, pre, suc, data):
		if root:
			if root.key < data and (pre[0] == None or root.key > pre[0].key):
				pre[0] = root
			if root.key > data and (suc[0] == None or root.key < suc[0].key):
				suc[0] = root
			find(root.left, pre, suc, data)
			find(root.right, pre, suc, data)
		return
	find(root, pre, suc, data)


def findPreSuc(root, pre, suc, key):

	def helper1(root):
		if not root:
			return
		if root.key < key:
			pre[0] = root
			helper1(root.right)
		else:
			helper1(root.left)

	def helper2(root):
		if not root:
			return
		if root.key > key:
			suc[0] = root
			helper2(root.left)
		else:
			helper2(root.right)
	helper1(root)
	helper2(root)
	return (pre[0], suc[0])


def findPreSuc(root, pre, suc, key):
	prev = root
	succ = root
	node = root

	def find_biggest(node):
		rv = node
		while node is not None:
			rv = node
			node = node.right
		return rv

	def find_smallest(node):
		rv = node
		while node is not None:
			rv = node
			node = node.left
		return rv
	while node is not None:
		if key == node.key:
			if node.left:
				prev = find_biggest(node.left)
			if node.right:
				succ = find_smallest(node.right)
			break
		elif key < node.key:
			succ = node
			node = node.left
		elif key > node.key:
			prev = node
			node = node.right
	pre[0] = prev
	suc[0] = succ
	if pre[0] is not None and pre[0].key >= key:
		pre[0] = Node(-1)
	if pre[0] is not None and suc[0].key <= key:
		suc[0] = Node(-1)


def findPreSuc(root, pre, suc, key):
	(l1, l2) = ([], [])

	def floor(root, l, k):
		if root == None:
			return
		if root.key >= k:
			floor(root.left, l, k)
		if root.key < k:
			if len(l) > 0:
				if l[0].key < root.key:
					l.pop()
					l.append(root)
			if len(l) == 0:
				l.append(root)
			floor(root.right, l, k)

	def ceil(root, l, k):
		if root == None:
			return
		if root.key <= k:
			ceil(root.right, l, k)
		if root.key > k:
			if len(l) > 0:
				if l[0].key > root.key:
					l.pop()
					l.append(root)
			if len(l) == 0:
				l.append(root)
			ceil(root.left, l, k)
	floor(root, l1, key)
	ceil(root, l2, key)
	if l1 != []:
		pre[0] = l1[0]
	if l2 != []:
		suc[0] = l2[0]


def get_pred(root):
	root = root.left
	while root.right:
		root = root.right
	return root

def get_succ(root):
	root = root.right
	while root.left:
		root = root.left
	return root

def findPreSuc(root, pre, suc, key):
	if root is None:
		return
	if root.key == key:
		if root.left:
			pre[0] = get_pred(root)
		if root.right:
			suc[0] = get_succ(root)
		return
	if key < root.key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	else:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)


def findPreSuc(root, pre_val, succ_val, key):
	if root is None:
		return
	if root.key == key:
		if root.left is not None:
			pre_val[0] = predecessor(root)
		if root.right is not None:
			succ_val[0] = successor(root)
	if root.key > key:
		succ_val[0] = root
		findPreSuc(root.left, pre_val, succ_val, key)
	if root.key < key:
		pre_val[0] = root
		findPreSuc(root.right, pre_val, succ_val, key)

def predecessor(node):
	pre = node.left
	while pre.right is not None:
		pre = pre.right
	return pre

def successor(node):
	succ = node.right
	while succ.left is not None:
		succ = succ.left
	return succ


def inorder(root, ans):
	if root == None:
		return
	inorder(root.left, ans)
	ans.append(root)
	inorder(root.right, ans)

def findPreSuc(root, pre, suc, key):
	ans = []
	inorder(root, ans)
	for i in range(len(ans)):
		if ans[i].key > key:
			suc[0] = ans[i]
			if i != 0:
				if ans[i - 1].key != key:
					pre[0] = ans[i - 1]
				elif i > 1:
					pre[0] = ans[i - 2]
			return
	if ans[-1].key != key:
		pre[0] = ans[-1]
	else:
		pre[0] = ans[-2]


def predecessor(root, pre, key):
	if root is None:
		return
	if root.key >= key:
		predecessor(root.left, pre, key)
	else:
		if pre[0] is None:
			pre[0] = root
		else:
			pre[0] = max((pre[0], root), key=lambda x: x.key)
		predecessor(root.right, pre, key)

def successor(root, suc, val):
	if root is None:
		return
	if root.key <= val:
		successor(root.right, suc, val)
	else:
		if suc[0] is None:
			suc[0] = root
		else:
			suc[0] = min((suc[0], root), key=lambda x: x.key)
		successor(root.left, suc, val)

def findPreSuc(root, pre, suc, key):
	(pre[0], suc[0]) = (None, None)
	predecessor(root, pre, key)
	successor(root, suc, key)


def findPreSuc(root, pre, suc, key):

	def helper(root):
		if root is None:
			return None
		if root.key == key:
			if root.left:
				tmp = root.left
				while tmp.right:
					tmp = tmp.right
				pre[0] = tmp
			if root.right:
				tmp = root.right
				while tmp.left:
					tmp = tmp.left
				suc[0] = tmp
			return
		if root.key > key:
			suc[0] = root
			helper(root.left)
		else:
			pre[0] = root
			helper(root.right)
	helper(root)


def store(root, inorder):
	if root is None:
		return
	store(root.left, inorder)
	inorder.append(root.key)
	store(root.right, inorder)

def findPreSuc(root, pre, suc, key):
	arr = []
	info = {}
	store(root, arr)
	if key not in arr:
		arr.append(key)
		arr = sorted(arr)
	for itr in range(0, len(arr)):
		info[arr[itr]] = itr
	idx = info[key]
	if idx - 1 >= 0:
		pre[0] = Node(arr[idx - 1])
	if idx + 1 < len(arr):
		suc[0] = Node(arr[idx + 1])


import bisect

def findPreSuc(root, pre, suc, key):

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

	def findthesucc(root):
		if root == None:
			return None
		if root.left == None:
			return root
		return findthesucc(root.left)

	def findthenode(root, key):
		if root == None:
			return
		if root.key == key:
			if root.left:
				val = findthepred(root.left)
				pre[0] = val if val != None else None
			if root.right:
				val = findthesucc(root.right)
				suc[0] = val if val != None else None
			return
		if root.key > key:
			suc[0] = root
			findthenode(root.left, key)
		else:
			pre[0] = root
			findthenode(root.right, key)
		return
	findthenode(root, key)


import bisect

def findPreSuc(root, pre, suc, key):
	inorder = []
	res = []

	def findinorder(root):
		if root == None:
			return
		findinorder(root.left)
		temp = Node(root.key)
		inorder.append(temp)
		res.append(root.key)
		findinorder(root.right)
	findinorder(root)
	ind = bisect.bisect_left(res, key)
	if ind - 1 >= 0:
		pre[0] = inorder[ind - 1]
	else:
		pre[0] = None
	ind = bisect.bisect_right(res, key)
	if ind < len(res):
		suc[0] = inorder[ind]
	else:
		suc[0] = None


def findPreSuc(root, pre, suc, key):
	if not root:
		return None
	if root.key == key:
		if root.left:
			pre[0] = predecesor(root.left)
		if root.right:
			suc[0] = successor(root.right)
	elif root.key > key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	elif root.key < key:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)

def predecesor(root):
	pred = root
	while pred.right:
		pred = pred.right
	return pred

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


def findPreSuc(root, pre, suc, key):
	pre[0] = Node(float('-inf'))
	suc[0] = Node(float('inf'))

	def inorder(node):
		if node is None:
			return
		inorder(node.left)
		if node.key < key:
			pre[0] = pre[0] if pre[0].key > node.key else node
		elif node.key > key:
			suc[0] = suc[0] if suc[0].key < node.key else node
		inorder(node.right)
	inorder(root)
	pre[0] = None if pre[0].key == float('-inf') else pre[0]
	suc[0] = None if suc[0].key == float('inf') else suc[0]


def dfs(node, key, pre, suc, prev):
	if not node:
		return
	if dfs(node.left, key, pre, suc, prev):
		return True
	if prev[0] < key and node.key > key:
		pre[0] = Node(prev[0])
		suc[0] = node
		return True
	if key != node.key:
		prev[0] = node.key
	if dfs(node.right, key, pre, suc, prev):
		return True

def findPreSuc(root, pre, suc, key):
	prev = [-1]
	if not dfs(root, key, pre, suc, prev):
		pre[0] = Node(prev[0])


def findPreSuc(root, pre, suc, key):

	def successful(root, key, pre, suc):
		if not root:
			return None
		if key < root.key:
			suc[0] = root
			successful(root.left, key, pre, suc)
		elif key > root.key:
			pre[0] = root
			successful(root.right, key, pre, suc)
		else:
			if root.left:
				pre[0] = pred(root.left)
			if root.right:
				suc[0] = succ(root.right)
			return

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

	def succ(root):
		while root.left:
			root = root.left
		return root
	successful(root, key, pre, suc)


def findPreSuc(root, pre, suc, key):
	if root == None:
		return
	temp = root
	while temp != None and temp.key != key:
		if temp.key > key:
			suc[0] = temp
			temp = temp.left
		elif temp.key < key:
			pre[0] = temp
			temp = temp.right
	if temp == None:
		return
	leftTree = temp.left
	while leftTree != None:
		pre[0] = leftTree
		leftTree = leftTree.right
	rightTree = temp.right
	while rightTree != None:
		suc[0] = rightTree
		rightTree = rightTree.left


def findPreSuc(root, pre, suc, key):

	def successor(root):
		while root is not None:
			if root.key <= key:
				root = root.right
			else:
				suc[0] = root
				root = root.left

	def predecessor(root):
		while root is not None:
			if root.key >= key:
				root = root.left
			else:
				pre[0] = root
				root = root.right
	successor(root)
	predecessor(root)


def findPreSuc(root, pre, suc, key):
	(pre[0], suc[0]) = (Node(-1), Node(-1))
	previous = Node(float('-inf'))
	next = Node(float('inf'))

	def inorder(root):
		if root is None:
			return
		inorder(root.left)
		nonlocal previous, next
		if root.key < key:
			previous.key = max(previous.key, root.key)
		elif root.key > key:
			next.key = min(next.key, root.key)
		inorder(root.right)
	inorder(root)
	if previous.key != float('-inf'):
		pre[0] = previous
	if next.key != float('inf'):
		suc[0] = next


def get_max(root):
	temp = root
	while temp.right:
		temp = temp.right
	return temp

def get_min(root):
	temp = root
	while temp.left:
		temp = temp.left
	return temp

def findPreSuc(root, pre, suc, key):
	temp = root
	while temp:
		if temp.key < key:
			if pre[0] is None or pre[0].key < temp.key:
				pre[0] = temp
			temp = temp.right
		elif temp.key > key:
			if suc[0] is None or suc[0].key > temp.key:
				suc[0] = temp
			temp = temp.left
		else:
			if temp.right is None and temp.left is not None:
				pre[0] = get_max(temp.left)
				return
			if temp.right is not None and temp.left is None:
				suc[0] = get_min(temp.right)
				return
			if temp.left and temp.right:
				pre[0] = get_max(temp.left)
				suc[0] = get_min(temp.right)
				return
			if temp.left is None and temp.right is None:
				return


def findPreSuc(root, pre, suc, key):
	prev = None
	stack = []
	count = 2
	while root != None or len(stack) != 0:
		while root != None:
			stack.append(root)
			root = root.left
		root = stack.pop()
		if root.key < key:
			pre[0] = root
		if root.key > key:
			suc[0] = root
			count = 0
			return
		prev = root
		root = root.right


def InorderPredecessor(root):
	if root.left == None:
		return None
	temp = root.left
	while temp.right != None:
		temp = temp.right
	return temp

def InorderSuccessor(root):
	if root.right == None:
		return None
	temp = root.right
	while temp.left != None:
		temp = temp.left
	return temp

def findPreSuc(root, pre, suc, key):
	temp = root
	while temp != None:
		if temp.key == key:
			p = InorderPredecessor(temp)
			s = InorderSuccessor(temp)
			if p != None:
				pre[0] = p
			if s != None:
				suc[0] = s
			return
		elif temp.key > key:
			suc[0] = temp
			temp = temp.left
		else:
			pre[0] = temp
			temp = temp.right


def findPreSuc(root, pre, suc, key):
	while root:
		if root.key == key:
			if root.left:
				temp = root.left
				while temp and temp.right:
					temp = temp.right
				pre[0] = temp
			if root.right:
				temp = root.right
				while temp and temp.left:
					temp = temp.left
				suc[0] = temp
			return
		if root.key < key:
			pre[0] = root
			root = root.right
		else:
			suc[0] = root
			root = root.left


def inorder(root):
	if root is None:
		return []
	return inorder(root.left) + [root] + inorder(root.right)

def findPreSuc(root, pre, suc, key):
	inord = inorder(root)
	n = len(inord)
	for i in range(n):
		if inord[i].key == key:
			pre[0] = inord[i - 1] if i != 0 else pre[0]
			suc[0] = inord[i + 1] if i != n - 1 else suc[0]
			break
		elif inord[i].key > key:
			pre[0] = inord[i - 1] if i != 0 else pre[0]
			suc[0] = inord[i]
			break
	if pre[0] is None and suc[0] is None:
		pre[0] = inord[-1]

def findPreSuc(root, pre, suc, key):
	while root:
		if root.key == key:
			if root.left:
				temp = root.left
				while temp and temp.right:
					temp = temp.right
				pre[0] = temp
			if root.right:
				temp = root.right
				while temp and temp.left:
					temp = temp.left
				suc[0] = temp
			return
		if root.key < key:
			pre[0] = root
			root = root.right
		else:
			suc[0] = root
			root = root.left


def get_predecessor(root):
	temp = root.left
	while temp and temp.right:
		temp = temp.right
	return temp

def get_successor(root):
	temp = root.right
	while temp and temp.left:
		temp = temp.left
	return temp

def findPreSuc(root, pre, suc, key):
	if root == None:
		return
	if root.key == key:
		if root.left:
			pre[0] = get_predecessor(root)
		if root.right:
			suc[0] = get_successor(root)
	elif key < root.key:
		suc[0] = root
		findPreSuc(root.left, pre, suc, key)
	else:
		pre[0] = root
		findPreSuc(root.right, pre, suc, key)


def inorder(root):
	if root == None:
		return []
	return inorder(root.left) + [root] + inorder(root.right)

def findPreSuc(root, pre, suc, key):
	data = inorder(root)
	for i in range(len(data)):
		if data[i].key == key:
			if i != 0:
				pre[0] = data[i - 1]
			if i + 1 < len(data):
				suc[0] = data[i + 1]
			break
		elif data[i].key > key:
			if i != 0:
				pre[0] = data[i - 1]
			suc[0] = data[i]
			break
	if pre[0] == None and suc[0] == None:
		pre[0] = data[-1]