Given a BST, and a reference to a Node x in the BST. Find the Inorder Successor of the given node in the BST.
 
Example 1:
Input:
      2
    /   \
   1     3
K(data of x) = 2
Output: 3 
Explanation: 
Inorder traversal : 1 2 3 
Hence, inorder successor of 2 is 3.
Example 2:
Input:
             20
            /   \
           8     22
          / \
         4   12
            /  \
           10   14
K(data of x) = 8
Output: 10
Explanation:
Inorder traversal: 4 8 10 12 14 20 22
Hence, successor of 8 is 10.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function inOrderSuccessor(). This function takes the root node and the reference node as argument and returns the node that is inOrder successor of the reference node. If there is no successor, return null value.
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 1000, where N is number of nodes

Difficulty: EASY
Tags: Data structures

Range queries
Skill types: Data structures

Range queries
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

'''
class Node:
    def __init__(self, val, k):
        self.right = None
        self.data = val
        self.left = None
        self.key = k
'''
class Solution:
    # returns the inorder successor of the Node x in BST (rooted at 'root')
    def inorderSuccessor(self, root, x):
        # Code here

Solutions:
class Solution:
	ans = 0

	def inorderSuccessor(self, root, x):
		ans = None
		while root != None:
			if root.data > x.data:
				ans = root
				root = root.left
			else:
				root = root.right
		return ans


class Solution:

	def inorderSuccessor(self, root, x):
		c = None
		while root is not None:
			if root.data > x.data:
				c = root
				root = root.left
			else:
				root = root.right
		return c


class Solution:

	def inorderSuccessor(self, root, p):
		if not root:
			return None
		if root.data <= p.data:
			return self.inorderSuccessor(root.right, p)
		return self.inorderSuccessor(root.left, p) or root

	def inOrderTraversal(self, root, n, succ):
		if root == None:
			return
		self.inOrderTraversal(root.left, n, succ)
		if root.data > n.data and (not succ.left):
			succ.left = root
			return
		self.inOrderTraversal(root.right, n, succ)


class Solution:

	def inorderSuccessor(self, root, n):
		succ = Node(0)
		self.inOrderTraversal(root, n, succ)
		return succ.left

	def inOrderTraversal(self, root, n, succ):
		if root == None:
			return
		self.inOrderTraversal(root.left, n, succ)
		if root.data > n.data and (not succ.left):
			succ.left = root
			return
		self.inOrderTraversal(root.right, n, succ)


class Solution:

	def min_right(self, root):
		if root == None:
			return None
		a = self.min_right(root.left)
		if a == None:
			return root
		else:
			return a

	def find(self, root, x):
		if x.data == root.data:
			return self.min_right(root.right)
		if x.data < root.data:
			a = self.find(root.left, x)
			if a == None:
				return root
			else:
				return a
		else:
			a = self.find(root.right, x)
			return a

	def inorderSuccessor(self, root, x):
		return self.find(root, x)


class Solution:

	def inorderSuccessor(self, root, x):
		res = []
		ans = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			res.append(root.data)
			ans.append(root)
			inorder(root.right)
		inorder(root)
		i = res.index(x.data)
		if i < len(res) - 1:
			return ans[i + 1]
		else:
			return None


class Solution:

	def inorderSuccessor(self, root, x):
		successor = None
		while root:
			if root.data <= x.data:
				root = root.right
			else:
				successor = root
				root = root.left
		return successor


class Solution:

	def inorderSuccessor(self, root, x):
		y = self.inorder(root, [])
		i = y.index(x.data)
		try:
			return Node(y[i + 1])
		except IndexError:
			return None

	def inorder(self, node, a):
		if node is None:
			return
		else:
			self.inorder(node.left, a)
			a.append(node.data)
			self.inorder(node.right, a)
		return a


class Solution:

	def minValue(self, node):
		while node.left:
			node = node.left
		return node

	def get_node(self, root, node):
		if not root:
			return None
		x = self.get_node(root.left, node)
		if x:
			return x
		if root.data == node.data:
			return root
		y = self.get_node(root.right, node)
		if y:
			return y

	def inorderSuccessor(self, root, x):
		x = self.get_node(root, x)
		if x.right is not None:
			return self.minValue(x.right)
		succ = None
		curr = root
		while curr and curr != x:
			if x.data > curr.data:
				curr = curr.right
			elif x.data <= curr.data:
				succ = curr
				curr = curr.left
		return succ


class Solution:

	def inorderSuccessor(self, root, x):
		stack = []
		curr = root
		prev = None
		while curr or stack:
			while curr:
				stack.append(curr)
				curr = curr.left
			curr = stack.pop()
			if prev and prev.data == x.data:
				return curr
			prev = curr
			curr = curr.right


class Solution:

	def inorderSuccessor(self, root, x):
		temp = root
		while temp:
			if temp.data == x.data:
				break
			elif temp.data > x.data:
				temp = temp.left
			else:
				temp = temp.right
		if temp is None:
			return None
		if temp.right:
			successor = self.find_min(temp.right)
		else:
			successor = self.find_ancestor(root, temp)
		return successor

	def find_min(self, node):
		while node.left:
			node = node.left
		return node

	def find_ancestor(self, root, node):
		successor = Node(-1)
		while root:
			if root.data < node.data:
				root = root.right
			elif root.data > node.data:
				successor = root
				root = root.left
			else:
				break
		return successor


class Solution:

	def inorderSuccessor(self, root, x):
		array = []
		self.inorder(root, array)
		for i in range(len(array)):
			if array[i].data == x.data:
				if len(array) == i + 1:
					return None
				else:
					return array[i + 1]

	def inorder(self, node, array):
		if node:
			self.inorder(node.left, array)
			array.append(node)
			self.inorder(node.right, array)


class Solution:

	def InOrder(self, root, x, suc):
		if root != None:
			self.InOrder(root.left, x, suc)
			if root.data > x.data:
				if suc[0] == None:
					suc[0] = root
			self.InOrder(root.right, x, suc)

	def inorderSuccessor(self, root, x):
		suc = [None]
		self.InOrder(root, x, suc)
		return suc[0]


class Solution:

	def inorderSuccessor(self, root, x):
		nextGreaterNode = None
		temp = root
		while temp:
			if x.data < root.data:
				nextGreaterNode = root
				root = root.left
			elif x.data == root.data:
				if root.right:
					focus = root.right
					while focus:
						if focus.left:
							focus = focus.left
						else:
							return focus
				else:
					return nextGreaterNode if nextGreaterNode else None
			else:
				root = root.right
		return None


class Solution:

	def inorderSuccessor(self, root, x):
		res = None
		while root is not None:
			if root.data == x.data:
				break
			elif root.data < x.data:
				root = root.right
			else:
				res = root
				root = root.left
		root = root.right
		while root is not None and root.left is not None:
			root = root.left
		if root is None:
			return res
		return root


class Solution:

	def inorderSuccessor(self, root, n):
		t = None
		while root != None:
			if n.data < root.data:
				t = root
				root = root.left
			else:
				root = root.right
		return t


class Solution:

	def inorderSuccessor(self, root, x):
		l = []
		self.inorder(root, l, x)
		if len(l) > 1:
			return l[-1]
		else:
			return

	def inorder(self, root, l, x):
		if not root:
			return
		self.inorder(root.left, l, x)
		if len(l) == 1:
			l.append(root)
			return
		if root.data == x.data:
			l.append(root)
		self.inorder(root.right, l, x)


class Solution:

	def inorderSuccessor(self, root, x):
		if not root or not x:
			return None
		succ = None
		v = root
		while v:
			if v.data <= x.data:
				v = v.right
			else:
				succ = v
				v = v.left
		return succ


class Solution:

	def left(self, root):
		if root.left is None:
			return root
		return self.left(root.left)

	def inorder(self, root, x):
		if root is None:
			return None
		if root.data == x.data:
			if root.right is not None:
				return self.left(root.right)
			return None
		if root.data > x.data:
			result = self.inorder(root.left, x)
			if result is None:
				return root
			return result
		else:
			result = self.inorder(root.right, x)
			return result

	def inorderSuccessor(self, root, x):
		return self.inorder(root, x)


class Node:

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

def innorder(root):
	if not root:
		return []
	return innorder(root.left) + [root] + innorder(root.right)

class Solution:

	def inorderSuccessor(self, root, x):
		a = innorder(root)
		for i in range(len(a) - 1):
			if a[i].data == x.data:
				return a[i + 1]


class Solution:

	def inorderSuccessor(self, root, x):

		def inorder(tree, arr):
			if tree is not None:
				inorder(tree.left, arr)
				arr.append(tree)
				inorder(tree.right, arr)
			return arr
		array = inorder(root, [])
		for i in range(len(array)):
			if array[i].data == x.data and i + 1 < len(array):
				return array[i + 1]
		return


class Solution:

	def inorderSuccessor(self, root, x):
		re = []

		def trav(rot):
			if rot.left is not None:
				trav(rot.left)
			re.append(rot)
			if rot.right is not None:
				trav(rot.right)
		trav(root)
		for i in range(len(re)):
			if re[i].data == k:
				if i + 1 < len(re):
					return re[i + 1]


class Solution:

	def inorderSuccessor(self, root, x):
		self.ans = None

		def helper(root, x):
			if root is None:
				return
			if root.data <= x.data:
				helper(root.right, x)
			else:
				if self.ans is None:
					self.ans = root
				else:
					self.ans = min((root, self.ans), key=lambda m: m.data)
				helper(root.left, x)
		helper(root, x)
		return self.ans


class Solution:

	def inorderSuccessor(self, root, x):
		(self.ans, self.x) = (None, False)

		def helper(root, x):
			if root is None:
				return
			helper(root.left, x)
			if self.x and self.ans is None:
				self.ans = root
				return
			if root.data == x.data:
				self.x = True
			helper(root.right, x)
		helper(root, x)
		return self.ans


class Solution:

	def inorderSuccessor(self, root, x):
		curr = root
		succ = 999989
		while curr:
			if curr.data > x.data:
				succ = curr.data
				curr = curr.left
			elif curr.data <= x.data:
				curr = curr.right
		if succ == 999989:
			return Node(-1)
		return Node(succ)


class Solution:

	def inorderSuccessor(self, root, x):
		succ = None
		temp = x.data
		while True:
			if root == None:
				return succ
			elif root.data > temp:
				succ = root
				root = root.left
			else:
				root = root.right


import sys

class Solution:

	def inorderSuccessor(self, root, x):
		ans = None
		while root:
			if root.data <= x.data:
				root = root.right
			else:
				ans = root
				root = root.left
		return ans


import sys

class Solution:

	def inorderSuccessor(self, root, x):
		arr_inorder = []

		def inorder(r):
			nonlocal arr_inorder
			if not r:
				return
			inorder(r.left)
			arr_inorder.append(r)
			inorder(r.right)
		inorder(root)
		for i in range(len(arr_inorder)):
			if arr_inorder[i].data == x.data:
				return None if i + 1 >= len(arr_inorder) else arr_inorder[i + 1]
		return None


class Solution:

	def inorderSuccessor(self, root, x):
		node = root
		succ = Node(-1)
		while node:
			if node.data <= x.data:
				node = node.right
			else:
				succ = node
				node = node.left
		return succ
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
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		k = int(input())
		ptr = Solution().inorderSuccessor(root, Node(k))
		if ptr is None:
			print(-1)
		else:
			print(ptr.data)


class Solution:

	def inorderSuccessor(self, root, x):

		def vamsi(root, x, ans):
			if not root:
				return None
			vamsi(root.left, x, ans)
			if x.data < root.data:
				ans.append(root.data)
				return
			vamsi(root.right, x, ans)
		ans = []
		vamsi(root, x, ans)
		return Node(ans[0]) if len(ans) > 0 else None


class Solution:

	def inorderSuccessor(self, root, x):
		succ = Node(-1)
		while root:
			if x.data >= root.data:
				root = root.right
			else:
				succ = root
				root = root.left
		return succ


class Solution:

	def inorderSuccessor(self, root, x):
		b = []
		c = []
		Solution.bst(root, b, c)
		if x.data in b:
			if b.index(x.data) >= len(b) - 1:
				return None
			return c[b.index(x.data) + 1]
		return None

	def bst(root, x, y):
		if root.left:
			Solution.bst(root.left, x, y)
		x.append(root.data)
		y.append(root)
		if root.right:
			Solution.bst(root.right, x, y)


class Solution:

	def inorderSuccessor(self, root, x):
		self.successor = None

		def helper(root, x):
			if root == None:
				return
			if root.data == x:
				helper(root.right, x)
			elif root.data > x:
				self.successor = root
				helper(root.left, x)
			else:
				helper(root.right, x)
		helper(root, x.data)
		return self.successor


class Solution:

	def solve(self, root, x, suc, first):
		if root is None:
			return
		self.solve(root.left, x, suc, first)
		if len(suc) == 1:
			suc.append(root)
			return
		if root.data == x.data:
			suc.append(root)
		self.solve(root.right, x, suc, first)
		return suc

	def inorderSuccessor(self, root, x):
		first = None
		suc = []
		self.solve(root, x, suc, first)
		if len(suc) > 1:
			return suc[-1]
		else:
			return


class Solution:

	def inorderSuccessor(self, root, x):
		l = []

		def inorder(root):
			if root is not None:
				inorder(root.left)
				l.append(root.data)
				inorder(root.right)
		inorder(root)
		m = x.data
		s = l.index(m)
		if m == l[-1]:
			return Node(-1)
		return Node(l[s + 1])


class Solution:

	def inorderSuccessor(self, root, x):
		self.suc = None

		def find(node):
			if node:
				find(node.left)
				if node.data > x.data and self.suc == None:
					self.suc = node
				find(node.right)
		find(root)
		return self.suc


class Solution:

	def __init__(self):
		self.ans = None

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


class Solution:

	def inorderSuccessor(self, root, x):
		x = self.findNode(root, x)
		if x == -1:
			return None
		elif x.right:
			curr = x.right
			while curr:
				if not curr.left:
					break
				curr = curr.left
			return curr
		else:
			succ = None
			while root:
				if root.data < x.data:
					root = root.right
				elif root.data > x.data:
					succ = root
					root = root.left
				else:
					break
			return succ

	def findNode(self, root, node):
		curr = root
		while curr:
			if curr.data < node.data:
				curr = curr.right
			elif curr.data > node.data:
				curr = curr.left
			else:
				return curr
		return -1


class Solution:

	def inorderSuccessor(self, root, x):
		(curr, nextBiggest) = (root, None)
		while curr:
			if curr.data <= x.data:
				curr = curr.right
			else:
				nextBiggest = curr
				curr = curr.left
		return nextBiggest


class Solution:

	def inorderSuccessor(self, root, x):
		ans = None

		def findNode(node):
			nonlocal ans
			if not node:
				return
			if node.data > x.data:
				ans = node
				return findNode(node.left)
			elif node.data < x.data:
				return findNode(node.right)
			else:
				return node
		node = findNode(root)
		if not node:
			return None

		def successor(node):
			if not node:
				return None
			if node.left:
				return successor(node.left)
			else:
				return node
		inter = successor(node.right)
		if not inter or inter.data < 0:
			return ans
		return inter


class Solution:

	def inorderSuccessor(self, root, x):
		currentNode = root
		if currentNode is None:
			return None
		while currentNode is not None:
			if currentNode.data == x.data:
				break
			elif currentNode.data > x.data:
				currentNode = currentNode.left
			else:
				currentNode = currentNode.right
		if currentNode.right is not None:
			successorNode = currentNode.right
			while successorNode.left is not None:
				successorNode = successorNode.left
			return successorNode
		successorNode = None
		ancestorNode = root
		while currentNode != ancestorNode:
			if currentNode.data < ancestorNode.data:
				successorNode = ancestorNode
				ancestorNode = ancestorNode.left
			else:
				ancestorNode = ancestorNode.right
		return successorNode


class Solution:

	def inorderSuccessor(self, root, x):
		curr = root
		while curr.data != x.data and curr:
			if x.data < curr.data:
				curr = curr.left
			if x.data > curr.data:
				curr = curr.right
		if curr is None:
			return -1
		ptr = curr
		if curr.right:
			curr = curr.right
			while curr.left:
				curr = curr.left
			return curr
		else:
			succ = Node(-1)
			while root:
				if root.data < x.data:
					root = root.right
				elif root.data > x.data:
					succ = root
					root = root.left
				else:
					break
		return succ


class Solution:

	def inorderSuccessor(self, root, X):
		if root is None or X is None:
			return None
		succ = None
		while root is not None:
			if root.data <= X.data:
				root = root.right
			else:
				succ = root
				root = root.left
		return succ


class Solution:

	def inorderSuccessor(self, root, x):
		inorder = []

		def fun(root, x):
			if root:
				fun(root.left, x)
				inorder.append(root.data)
				fun(root.right, x)
		fun(root, x)
		for i in range(0, len(inorder)):
			if inorder[i] == x.data:
				if i < len(inorder) - 1:
					return Node(inorder[i + 1])
				else:
					return None
		return None


class Solution:

	def inorderSuccessor(self, root, x):
		if not root:
			return None
		curr = root
		stack = []
		flag = False
		while True:
			if curr is not None:
				stack.append(curr)
				curr = curr.left
			elif stack:
				if flag:
					return stack.pop()
				curr = stack.pop()
				if curr.data == x.data:
					flag = True
				curr = curr.right
			else:
				return None


class Solution:

	def inorderSuccessor(self, root, x):
		stack = [root]
		num = float('inf')
		if root.data > x.data:
			num = root.data
		save_node = root
		while len(stack) != 0:
			node = stack.pop()
			l = node.left
			r = node.right
			if l:
				stack.append(l)
				if x.data < l.data and num > l.data:
					num = l.data
					save_node = l
			if r:
				stack.append(r)
				if x.data < r.data and num > r.data:
					num = r.data
					save_node = r
		if num == float('inf'):
			return None
		else:
			return save_node


class Solution:

	def inorderSuccessor(self, root, x):
		s = []
		t1 = Node(None)
		while 1:
			if root is not None:
				s.append(root)
				root = root.left
			elif s:
				t = s.pop()
				if t1.data == x.data:
					return t
				else:
					t1 = t
				root = t.right
			else:
				break
		return None


class Solution:

	def inOr(self, root, arr, x, c):
		if not root:
			return
		self.inOr(root.left, arr, x, c)
		arr.append(root)
		if root.data == x.data:
			c = c + 1
		self.inOr(root.right, arr, x, c)

	def inorderSuccessor(self, root, x):
		arr = []
		self.inOr(root, arr, x, 0)
		i = 0
		for e in arr:
			if x.data == e.data:
				if i == len(arr) - 1:
					return None
				return arr[i + 1]
			i = i + 1


class Solution:

	def inorderSuccessor(self, root, x):
		curr = root
		stack = []
		while curr or stack:
			while curr:
				stack.append(curr)
				curr = curr.left
			curr = stack.pop()
			if curr.data == x.data:
				if curr.right:
					curr = curr.right
					while curr.left:
						curr = curr.left
					return curr
				elif stack:
					return stack.pop()
				else:
					return None
			curr = curr.right
		return None


class Solution:

	def inorderSuccessor(self, root, x):

		def helper(node, x, succ):
			if not node:
				return
			helper(node.left, x, succ)
			if node.data > x.data and (not succ.left):
				succ.left = node
				return
			helper(node.right, x, succ)
		if not root:
			return None
		succ = Node(0)
		helper(root, x, succ)
		return succ.left


class Solution:

	def inorderSuccessor(self, root, x):
		if not root:
			return None
		stack = []
		prev = 0
		while stack or root:
			while root:
				stack.append(root)
				root = root.left
			node = stack.pop()
			if prev == x.data:
				return node
			prev = node.data
			root = node.right
		return None


class Solution:

	def inorderSuccessor(self, root, x):

		def inorder(List, root):
			if not root:
				return
			inorder(List, root.left)
			List.append(root.data)
			inorder(List, root.right)
		List = []
		inorder(List, root)
		if x.data in List:
			I = List.index(x.data)
		else:
			return None
		if I < len(List) - 1:
			return Node(List[I + 1])
		else:
			return None


class Solution:

	def inorderSuccessor(self, root, x):
		arr = []

		def inorder(node):
			if not node:
				return
			inorder(node.left)
			arr.append(node.data)
			inorder(node.right)
		inorder(root)
		for i in range(0, len(arr)):
			if arr[i] > x.data:
				return Node(arr[i])


class Solution:

	def inorderSuccessor(self, root, x):

		def inorder(node):
			if node == None:
				return []
			else:
				return inorder(node.left) + [node.data] + inorder(node.right)
		l = inorder(root)
		ans = None
		for i in range(len(l)):
			if l[i] == x.data:
				if i == len(l) - 1:
					return None
				ans = l[i + 1]
				break

		def search(node, ans):
			if node == None:
				return
			if node.data < ans:
				return search(node.right, ans)
			elif node.data > ans:
				return search(node.left, ans)
			else:
				return node
		return search(root, ans)


class Solution:

	def inorderSuccessor(self, root, x):
		l = []

		def search(node, ans):
			l.append(node)
			if node == None:
				return
			if node.data < ans:
				return search(node.right, ans)
			elif node.data > ans:
				return search(node.left, ans)
			else:
				return node
		se = search(root, x.data)
		if se.right != None:
			temp = se.right
			while temp.left:
				temp = temp.left
			l.append(temp)
		mini = 99999999999999999999999
		ans = None
		for i in l:
			if i.data > x.data and i.data < mini:
				mini = i.data
				ans = i
		return ans


import sys

class Solution:

	def inorderSuccessor(self, root, x):
		maxi = [sys.maxsize]
		self.f(root, x, maxi)
		if maxi[0] == sys.maxsize:
			return None
		else:
			return Node(maxi[0])

	def f(self, root, x, maxi):
		if root == None:
			return
		if x.data >= root.data:
			self.f(root.right, x, maxi)
		else:
			maxi[0] = min(maxi[0], root.data)
			self.f(root.left, x, maxi)


class Solution:

	def inorderSuccessor(self, root, x):
		self.a = list()
		new = Node(-1)

		def postorder(root, x):
			if root == None:
				return -1
			postorder(root.left, x)
			self.a.append(root.data)
			postorder(root.right, x)
			return self.a
		postorder(root, x)
		for i in range(len(self.a) - 1):
			if self.a[i] == x.data:
				new = Node(self.a[i + 1])
				break
		return new


class Solution:

	def inorderSuccessor(self, root, x):
		suc = None
		while root:
			if root.data <= x.data:
				root = root.right
			elif root.data > x.data:
				suc = root
				root = root.left
		return suc


class Solution:

	def inorderSuccessor(self, root, x):

		def f(r, x, s):
			if r == None:
				return s
			elif r.data <= x.data:
				return f(r.right, x, s)
			else:
				s = r
				return f(r.left, x, s)
		ans = f(root, x, None)
		return ans


class Solution:

	def inorder(self, root, A, tgt):
		if not root:
			return
		self.inorder(root.left, A, tgt)
		A.append(root)
		if root.data == tgt[0]:
			tgt[1] = len(A) - 1
		self.inorder(root.right, A, tgt)

	def inorderSuccessor(self, root, x):
		tgt = [x.data, -1]
		path = []
		self.inorder(root, path, tgt)
		if tgt[1] + 1 >= len(path):
			return None
		return path[tgt[1] + 1]


class Solution:
	_successor = None
	_found = False

	def inorderSuccessor(self, root, x):
		if root:
			self.inorderSuccessor(root.left, x)
			if self._found:
				self._successor = root
				self._found = False
			if root.data == x.data:
				self._found = True
			self.inorderSuccessor(root.right, x)
		return self._successor


class Solution:

	def inorderSuccessor(self, root, x):

		def inorderTraverse(root, ans):
			if root:
				inorderTraverse(root.left, ans)
				ans.append(root)
				inorderTraverse(root.right, ans)
			return ans
		test = inorderTraverse(root, [])
		smallest = 999999999
		start = False
		node = Node(-1)
		for item in test:
			if item.data == x.data:
				start = True
			if start:
				if item.data != 'N' and x.data < item.data < smallest:
					smallest = item.data
					node = item
		return node