Given a Binary Search Tree and a target sum. Check whether there's a pair of Nodes in the BST with value summing up to the target sum. 
Example 1:
Input:
        2
      /   \
     1     3
sum = 5
Output: 1 
Explanation: 
Nodes with value 2 and 3 sum up to 5.
Example 2:
Input:
           6
          /    
         5     
        /
       3 
     /  \
    1    4
sum = 2
Output: 0 
Explanation: 
There's no pair that sums up to 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isPairPresent() that takes a root node and a target value as a parameter and returns 1 if there's a pair of Nodes in the BST with values summing up to the target sum, else returns 0. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 ≤ Number of Nodes ≤ 10^{5}
1 ≤ Sum ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None



'''



class Solution:

    # root : the root Node of the given BST

    # target : the target sum

    def isPairPresent(self,root, target): 

        # code here.

Solutions:
class Solution:

	def isPairPresent(self, root, target):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			ino.append(root.data)
			inorder(root.right)
		ino = []
		inorder(root)
		l = 0
		r = len(ino) - 1
		while l < r:
			if ino[l] + ino[r] == target:
				return 1
			elif ino[l] + ino[r] > target:
				r -= 1
			else:
				l = l + 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		stack1 = []
		stack2 = []
		(curr1, curr2) = (root, root)
		while True:
			if curr1 is not None or curr2 is not None:
				if curr1 is not None:
					stack1.append(curr1)
					curr1 = curr1.left
				if curr2 is not None:
					stack2.append(curr2)
					curr2 = curr2.right
			else:
				if len(stack1) == 0 or len(stack2) == 0:
					break
				left_top = stack1[-1]
				right_top = stack2[-1]
				if id(left_top) == id(right_top):
					break
				sumval = left_top.data + right_top.data
				if sumval < target:
					stack1.pop()
					curr1 = left_top.right
				elif sumval > target:
					stack2.pop()
					curr2 = right_top.left
				else:
					return 1
		return 0


from collections import Counter

class Solution:

	def isPairPresent(self, root, target):
		l = []

		def inorderTraversal(root):
			nonlocal l
			if root is not None:
				inorderTraversal(root.left)
				l.append(root.data)
				inorderTraversal(root.right)
		inorderTraversal(root)
		dic = Counter(l)
		for i in dic.keys():
			dic[i] -= 1
			x = target - i
			if x in dic.keys():
				return 1
			dic[i] += 1
		return 0


from collections import deque

class Solution:

	def isPairPresent(self, root, target):
		dictOfNum = {}
		queue = deque()
		queue.append(root)
		while queue:
			e = queue.popleft()
			if target - e.data in dictOfNum and dictOfNum[target - e.data] != e:
				return 1
			else:
				dictOfNum[e.data] = e
			if e.left:
				queue.append(e.left)
			if e.right:
				queue.append(e.right)
		return 0


class Solution:

	def isPairPresent(self, root, target):

		def inorder(root):
			nonlocal target, mp, ans
			if not root:
				return
			inorder(root.left)
			if root.data in mp:
				ans = 1
			else:
				mp[target - root.data] = 1
			inorder(root.right)
		mp = {}
		ans = 0
		inorder(root)
		return ans


class Solution:

	def isPairPresent(self, root, target):
		stack_left = []
		stack_right = []
		curr_left = root
		curr_right = root
		while True:
			while curr_left:
				stack_left.append(curr_left)
				curr_left = curr_left.left
			while curr_right:
				stack_right.append(curr_right)
				curr_right = curr_right.right
			if not stack_left or not stack_right or stack_left[-1] == stack_right[-1]:
				break
			left_val = stack_left[-1].data
			right_val = stack_right[-1].data
			if left_val + right_val == target:
				return 1
			elif left_val + right_val < target:
				curr_left = stack_left.pop().right
			else:
				curr_right = stack_right.pop().left
		return 0


class Solution:

	def isPairPresent(self, root, target):
		ans = []
		self.inorder(root, ans)
		left = 0
		right = len(ans) - 1
		while left < right:
			if ans[left] + ans[right] == target:
				return 1
			elif ans[left] + ans[right] < target:
				left += 1
			else:
				right -= 1
		return 0

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


class Solution:

	def isPairPresent(self, root, target):
		self.visited_list = []
		self.count = 0

		def BS(target, low=0, high=self.count - 1):
			if low <= high:
				mid = low + (high - low) // 2
				if self.visited_list[mid] > target:
					return BS(target, low, mid - 1)
				elif self.visited_list[mid] < target:
					return BS(target, mid + 1, high)
				else:
					return mid
			return -1

		def func(root, target):
			if root == None:
				return False
			lb = func(root.left, target)
			if BS(target - root.data, 0, self.count - 1) != -1:
				return True
			self.visited_list.append(root.data)
			self.count += 1
			rb = func(root.right, target)
			return lb or rb
		return 1 if func(root, target) else 0


class Solution:

	def isPairPresent(self, root, target):
		l = []

		def ino(root):
			if not root:
				return -1
			else:
				ino(root.left)
				l.append(root.data)
				ino(root.right)
		ino(root)
		i = 0
		j = len(l) - 1
		while i < j:
			if l[i] + l[j] == target:
				return 1
			elif l[i] + l[j] < target:
				i += 1
			else:
				j -= 1
		return 0


class BSTIterator:

	def __init__(self, root, isReverse):
		self.root = root
		self.reverse = isReverse
		self.st = []
		self.pushAll(root)

	def pushAll(self, curRoot):
		while curRoot:
			self.st.append(curRoot)
			if self.reverse:
				curRoot = curRoot.right
			else:
				curRoot = curRoot.left

	def next(self):
		curValue = self.st.pop()
		if self.reverse == False:
			self.pushAll(curValue.right)
		else:
			self.pushAll(curValue.left)
		return curValue.data

class Solution:

	def isPairPresent(self, root, target):

		def result(root, k):
			if root == None:
				return False
			l = BSTIterator(root, False)
			r = BSTIterator(root, True)
			i = l.next()
			j = r.next()
			while i < j:
				if i + j == k:
					return 1
				elif i + j < k:
					i = l.next()
				else:
					j = r.next()
			return 0
		return result(root, target)


class Solution:
	d = dict()

	def inorder(self, root):
		if root == None:
			return
		self.inorder(root.left)
		self.d[root.data] = 1
		self.inorder(root.right)

	def isPairPresent(self, root, target):
		self.d = dict()
		self.inorder(root)
		for i in self.d:
			if target - i in self.d:
				return 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		d = set()
		return self.helper(root, target, d)

	def helper(self, root, target, d):
		if root is None:
			return 0
		if root.data > target:
			return self.helper(root.left, target, d)
		elif target - root.data in d:
			return 1
		else:
			d.add(root.data)
			return self.helper(root.left, target, d) or self.helper(root.right, target, d)


class Solution:

	def isPairPresent(self, root, target):
		node_values = set()
		node_queue = []
		node_queue.append(root)
		if root is None:
			return 0
		while len(node_queue) > 0:
			node = node_queue.pop()
			if target - node.data in node_values:
				return 1
			else:
				node_values.add(node.data)
				if node.left is not None:
					node_queue.append(node.left)
				if node.right is not None:
					node_queue.append(node.right)
		return 0


class Solution:

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

	def isPairPresent(self, root, target):
		inorder = self.inorder(root, [])
		i = 0
		j = len(inorder) - 1
		while i < j:
			k = inorder[i] + inorder[j]
			if k < target:
				i += 1
			elif k > target:
				j -= 1
			else:
				return 1
		return 0


class Solution:

	def isPairPresent(self, root, k):
		self.inOrder = []
		self.inorder(root)
		(l, r) = (0, len(self.inOrder) - 1)
		while l < r:
			target = self.inOrder[l] + self.inOrder[r]
			if target == k:
				return 1
			elif target > k:
				r -= 1
			else:
				l += 1
		return 0

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

class BSTIterator:

	def __init__(self, root, isReverse):
		self.stack = []
		self.reverse = True
		self.reverse = isReverse
		self.pushAll(root)

	def next(self):
		curr = self.stack.pop()
		if self.reverse == False:
			self.pushAll(curr.right)
		else:
			self.pushAll(curr.left)
		return curr.data

	def pushAll(self, root):
		while root:
			self.stack.append(root)
			if self.reverse == True:
				root = root.right
			else:
				root = root.left

class Solution:

	def isPairPresent(self, root, k):
		if root is None:
			return 0
		l = BSTIterator(root, False)
		r = BSTIterator(root, True)
		(i, j) = (l.next(), r.next())
		while i < j:
			target = i + j
			if target == k:
				return 1
			elif target < k:
				i = l.next()
			else:
				j = r.next()
		return 0


class Solution:

	def isPairPresent(self, root, target):

		def trav(root, mp):
			if root == None:
				return None
			mp[root.data] = root.data
			if root.left:
				trav(root.left, mp)
			if root.right:
				trav(root.right, mp)
		mp = {}
		trav(root, mp)

		def travcheck(root, mp, target):
			if root == None:
				return None
			remaining = target - root.data
			if remaining in mp:
				return 1
			if root.left and travcheck(root.left, mp, target) or (root.right and travcheck(root.right, mp, target)):
				return 1
			return 0
		return travcheck(root, mp, target)


class Solution:

	def findleftNodes(self, root, stack):
		while root:
			stack.append(root)
			root = root.left
		return stack

	def findrightNodes(self, root, stack):
		while root:
			stack.append(root)
			root = root.right
		return stack

	def isPairPresent(self, root, target):
		leftStack = []
		rightStack = []
		self.findleftNodes(root, leftStack)
		self.findrightNodes(root, rightStack)
		while leftStack and rightStack:
			left_node = leftStack[-1]
			right_node = rightStack[-1]
			if left_node == right_node:
				break
			current_sum = left_node.data + right_node.data
			if current_sum == target:
				return 1
			elif current_sum < target:
				leftStack.pop()
				self.findleftNodes(left_node.right, leftStack)
			else:
				rightStack.pop()
				self.findrightNodes(right_node.left, rightStack)
		return 0


class Solution:

	def pushleft(self, st, root):
		while root:
			st.append(root)
			root = root.left

	def pushright(self, st, root):
		while root:
			st.append(root)
			root = root.right

	def nextleft(self, st):
		node = st.pop()
		self.pushleft(st, node.right)
		return node.data

	def nextright(self, st):
		node = st.pop()
		self.pushright(st, node.left)
		return node.data

	def isPairPresent(self, root, target):
		stleft = []
		stright = []
		self.pushleft(stleft, root)
		self.pushright(stright, root)
		(left, right) = (self.nextleft(stleft), self.nextright(stright))
		while left < right:
			if left + right == target:
				return 1
			if left + right < target:
				left = self.nextleft(stleft)
			elif left + right > target:
				right = self.nextright(stright)
		return 0


class Solution:

	def isPairPresent(self, root, target):
		flag = [0]
		seen = set()
		self.Helper(root, target, seen, flag)
		return flag[0]

	def Helper(self, root, target, seen, flag):
		if flag[0] == 1 or root is None:
			return
		if target - root.data in seen:
			flag[0] = 1
			return
		seen.add(root.data)
		self.Helper(root.left, target, seen, flag)
		self.Helper(root.right, target, seen, flag)


from collections import deque

class BSTiterator:

	def traverse(self, node, reverse):
		while node:
			self.stack.append(node)
			if reverse:
				node = node.right
			else:
				node = node.left

	def __init__(self, root, reverse):
		self.stack = deque()
		self.traverse(root, reverse)

	def next(self, reverse):
		if self.hasNext():
			node = self.stack.pop()
			ans = node.data
			if reverse:
				node = node.left
			else:
				node = node.right
			self.traverse(node, reverse)
			return ans

	def hasNext(self):
		if len(self.stack):
			return True
		return False

class Solution:

	def isPairPresent(self, root, target):
		a = BSTiterator(root, False)
		b = BSTiterator(root, True)
		i = a.next(False)
		j = b.next(True)
		while i < j:
			if i + j < target:
				i = a.next(False)
			elif i + j > target:
				j = b.next(True)
			else:
				return 1
		return 0


class Solution:

	def isPairPresent(self, root, k):
		if root is None:
			return False
		stack1 = []
		stack2 = []

		def dfs(node, stack, isLeft):
			if node is None:
				return
			stack.append(node)
			if isLeft:
				dfs(node.left, stack, isLeft)
			else:
				dfs(node.right, stack, isLeft)
		dfs(root, stack1, True)
		dfs(root, stack2, False)
		while stack1 and stack2 and (stack1[-1] != stack2[-1]):
			sum_ = stack1[-1].data + stack2[-1].data
			if sum_ == k:
				return 1
			if sum_ > k:
				dfs(stack2.pop().left, stack2, False)
			else:
				dfs(stack1.pop().right, stack1, True)
		return 0


class Solution:

	def isPairPresent(self, root, target):
		self.ans = 0
		self.s1 = set()

		def check(root):
			if root == None:
				return
			if target - root.data in self.s1:
				self.ans = 1
			self.s1.add(root.data)
			check(root.left)
			check(root.right)
		check(root)
		return self.ans


class Solution:

	def search(self, root, n):
		if root is None:
			return
		self.search(root.left, n)
		n.append(root.data)
		self.search(root.right, n)

	def isPairPresent(self, root, target):
		n = []
		self.search(root, n)
		i = 0
		j = len(n) - 1
		s = 0
		while i < j:
			s = n[i] + n[j]
			if s == target:
				return 1
			if s < target:
				i += 1
			if s > target:
				j -= 1
		return 0


from queue import Queue

class Solution:

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

	def isPairPresent(self, root, target):
		ar = []
		self.inOrder(root, ar)
		i = 0
		j = len(ar) - 1
		while i < j:
			temp = ar[i] + ar[j]
			if temp == target:
				return 1
			if temp > target:
				j -= 1
			else:
				i += 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		ll = []

		def inor(root):
			if root == None:
				return ll
			inor(root.left)
			ll.append(root.data)
			inor(root.right)
		inor(root)

		def search(arr, L, N):
			s = 0
			e = L - 1
			while s < e:
				if arr[s] + arr[e] == N:
					return 1
				if arr[s] + arr[e] < N:
					s += 1
				else:
					e -= 1
			return 0
		return search(ll, len(ll), target)


class Solution:

	def findpair(self, node, mp, target):
		if node == None:
			return False
		if target - node.data in mp:
			return True
		mp.add(node.data)
		return self.findpair(node.left, mp, target) or self.findpair(node.right, mp, target)

	def isPairPresent(self, root, target):
		mp = set()
		if self.findpair(root, mp, target):
			return 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		if not root:
			return []
		stack = []
		res = set()
		while True:
			if root:
				stack.append(root)
				root = root.left
			elif stack:
				temp = stack.pop()
				if target - temp.data in res:
					return 1
				res.add(temp.data)
				root = temp.right
			else:
				break
		return 0


class Solution:

	def isPairPresent(self, root, target):
		values = set()
		stack = []
		curr = root
		while curr or stack:
			while curr:
				stack.append(curr)
				curr = curr.left
			curr = stack.pop()
			if target - curr.data in values:
				return 1
			values.add(curr.data)
			curr = curr.right
		return 0


class Solution:

	def isPairPresent(self, root, target):
		visited = set()

		def findPairs(node):
			if not node:
				return 0
			if target - node.data in visited:
				return 1
			visited.add(node.data)
			return findPairs(node.left) or findPairs(node.right)
		return findPairs(root)


class Solution:

	def check(self, root, k, d):
		if not root:
			return 0
		if self.check(root.left, k, d):
			return 1
		if k - root.data not in d:
			d[root.data] = 1
		else:
			return 1
		return self.check(root.right, k, d)

	def isPairPresent(self, root, target):
		d = {}
		return self.check(root, target, d)


class BSTiterator:

	def __init__(self, root):
		self.stackN = []
		curr = root
		while curr:
			self.stackN.append(curr)
			curr = curr.left
		self.stackB = []
		while root:
			self.stackB.append(root)
			root = root.right

	def next(self):
		node = self.stackN.pop()
		res = node.data
		node = node.right
		while node:
			self.stackN.append(node)
			node = node.left
		return res

	def before(self):
		node = self.stackB.pop()
		res = node.data
		if node.left:
			node = node.left
			while node:
				self.stackB.append(node)
				node = node.right
		return res

class Solution:

	def isPairPresent(self, Root, target):
		it = BSTiterator(Root)
		l = it.next()
		r = it.before()
		while l < r:
			if l + r < target:
				l = it.next()
			elif l + r > target:
				r = it.before()
			else:
				return 1
		return 0


class Solution:

	def isPairPresent(self, Root, target):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			nums.append(root.data)
			inorder(root.right)
		nums = []
		inorder(root)
		l = 0
		h = len(nums) - 1
		while l <= h:
			if nums[l] + nums[h] < target:
				l += 1
			elif nums[l] + nums[h] > target:
				h -= 1
			else:
				return 1
		return 0


class Solution:

	def isPairPresent(self, Root, target):

		def find(root, x):
			while root:
				if root.data > x:
					root = root.left
				elif root.data < x:
					root = root.right
				else:
					return 1
			return 0

		def f(root, target):
			if root == None:
				return 0
			if find(Root, target - root.data):
				return 1
			if f(root.left, target):
				return 1
			return f(root.right, target)
		return f(Root, target)


class InorderGenerator:

	def __init__(self, root):
		self.root = root
		self.cur = root
		self.stack = []

	def getNext(self):
		while self.cur:
			self.stack.append(self.cur)
			self.cur = self.cur.left
		if self.stack:
			lastNode = self.stack.pop()
			self.cur = lastNode.right
			return lastNode.data
		else:
			return None

class R_InorderGenerator:

	def __init__(self, root):
		self.root = root
		self.cur = root
		self.stack = []

	def getNext(self):
		while self.cur:
			self.stack.append(self.cur)
			self.cur = self.cur.right
		if self.stack:
			lastNode = self.stack.pop()
			self.cur = lastNode.left
			return lastNode.data
		else:
			return None

class Solution:

	def isPairPresent(self, root, target):
		inorder = InorderGenerator(root)
		rinorder = R_InorderGenerator(root)
		left = inorder.getNext()
		right = rinorder.getNext()
		while left is not None and right is not None:
			if left == right:
				return 0
			if left + right == target:
				return 1
			elif left + right > target:
				right = rinorder.getNext()
			else:
				left = inorder.getNext()
		return 0


class Solution:

	def isPairPresent(self, root, target):

		def dfs(node, s=set()):
			if not node:
				return 0
			if target - node.data in s:
				return 1
			s.add(node.data)
			return dfs(node.left, s) or dfs(node.right, s)
		return dfs(root, set())


class Solution:

	def isPairPresent(self, root, target):
		stack = []
		s = set()
		while True:
			if root:
				stack.append(root)
				root = root.left
			elif stack:
				root = stack.pop()
				if target - root.data in s:
					return 1
				else:
					s.add(root.data)
				root = root.right
			else:
				return 0


class Solution:

	def isPairPresent(self, root, target):
		arr = self.inOrderTraversal(root)
		n = len(arr)
		j = n - 1
		for i in range(n):
			while j > i and arr[i] + arr[j] > target:
				j -= 1
			if i >= j:
				return 0
			if arr[i] + arr[j] == target:
				return 1

	def inOrderTraversal(self, root):
		if root is None:
			return []
		output = self.inOrderTraversal(root.left)
		output.append(root.data)
		output += self.inOrderTraversal(root.right)
		return output


class Solution:

	def isPairPresent(self, root, target):

		def until(root, sum1, p):
			if root == None:
				return False
			if until(root.left, sum1, p) == True:
				return True
			if sum1 - root.data in p:
				return True
			p.add(root.data)
			return until(root.right, sum1, p)
		p = set()
		if until(root, target, p):
			return 1
		else:
			return 0


class Solution:

	def isPairPresent(self, root, k):
		c = {}

		def f(root):
			if not root:
				return
			if f(root.left):
				return 1
			if k - root.data in c:
				return 1
			c[root.data] = 1
			if f(root.right):
				return 1
			return 0
		return f(root)


class Solution:

	def isPairPresent(self, root, target):
		dic = {}
		ans = False

		def iterate(root, target):
			nonlocal dic, ans
			if root is None:
				return
			if target - root.data in dic:
				ans = True
			else:
				dic[root.data] = 1
			iterate(root.left, target)
			iterate(root.right, target)
		iterate(root, target)
		return 1 if ans else 0


class Solution:

	def isPairPresent(self, root, target):
		arr = []

		def inOrderList(root):
			if root is None:
				return
			inOrderList(root.left)
			arr.append(root.data)
			inOrderList(root.right)
		inOrderList(root)
		i = 0
		j = len(arr) - 1
		while i < j:
			if arr[i] + arr[j] > target:
				j -= 1
			elif arr[i] + arr[j] < target:
				i += 1
			elif arr[i] + arr[j] == target:
				return 1
				break
		return 0


class Solution:

	def isPairPresent(self, root, k):
		s = []
		e = []
		curr = root
		rcurr = root

		def nextleft() -> int:
			nonlocal curr
			nonlocal s
			while curr:
				s.append(curr)
				curr = curr.left
			elmt = s.pop()
			curr = elmt.right
			return elmt.data

		def nextright() -> int:
			nonlocal rcurr
			nonlocal e
			while rcurr:
				e.append(rcurr)
				rcurr = rcurr.right
			elmt = e.pop()
			rcurr = elmt.left
			return elmt.data
		left = nextleft()
		right = nextright()
		while left < right:
			if left + right == k:
				return 1
			if left + right < k:
				left = nextleft()
			else:
				right = nextright()
		return 0


class Solution:

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

	def isPairPresent(self, root, target):
		inorder = self.inorder(root, [])
		s = 0
		e = len(inorder) - 1
		while s < e:
			sum = inorder[s] + inorder[e]
			if sum > target:
				e -= 1
			elif sum < target:
				s += 1
			else:
				return 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		a = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			a.append(root.data)
			inorder(root.right)
		inorder(root)
		i = 0
		j = len(a) - 1
		ans = 0
		while i < j:
			if a[i] + a[j] == target:
				ans = 1
				break
			elif a[i] + a[j] < target:
				i = i + 1
			else:
				j = j - 1
		return ans


class Solution:

	def __init__(self):
		self.dp = dict()
		self.ans = 0

	def tr(self, root, target):
		if root == None:
			return
		if self.dp.get(target - root.data) != None:
			self.ans = int(self.ans or 1)
		self.dp[root.data] = 1
		self.tr(root.left, target)
		self.tr(root.right, target)

	def isPairPresent(self, root, target):
		self.tr(root, target)
		return self.ans


class Solution:

	def isPairPresent(self, root, target):
		if root == None:
			return False
		self.s = set()
		self.ans = None

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			if target - root.data in self.s:
				self.ans = True
				return
			self.s.add(root.data)
			inorder(root.right)
		inorder(root)
		if self.ans:
			return 1
		else:
			return 0


class Solution:

	def inorder_iteratively(self, stack, resume_from_mid):
		while stack:
			top = stack[-1]
			if top.left and (not resume_from_mid):
				stack.append(top.left)
			else:
				while stack:
					popped_node = stack.pop()
					resume_from_mid = True
					if popped_node.right:
						stack.append(popped_node.right)
						resume_from_mid = False
					return [popped_node.data, stack, resume_from_mid]

	def backward_inorder_iteratively(self, stack, resume_from_mid):
		while stack:
			top = stack[-1]
			if top.right and (not resume_from_mid):
				stack.append(top.right)
			else:
				while stack:
					popped_node = stack.pop()
					resume_from_mid = True
					if popped_node.left:
						stack.append(popped_node.left)
						resume_from_mid = False
					return [popped_node.data, stack, resume_from_mid]

	def isPairPresent(self, root, target):
		(forward_stack, backward_stack, resume_from_mid) = ([root], [root], False)
		(front, back) = (self.inorder_iteratively(forward_stack, resume_from_mid), self.backward_inorder_iteratively(backward_stack, resume_from_mid))
		while front[0] != back[0]:
			if front[0] + back[0] == target:
				return 1
			elif front[0] + back[0] > target:
				back = self.backward_inorder_iteratively(back[1], back[2])
			else:
				front = self.inorder_iteratively(front[1], front[2])
		return 0


class Solution:

	def isPresent(self, root, target, h):
		if root is None:
			return 0
		if self.isPresent(root.left, target, h) or self.isPresent(root.right, target, h):
			return 1
		if target - root.data in h:
			return 1
		else:
			h.add(root.data)
			return 0

	def isPairPresent(self, root, target):
		h = set()
		return self.isPresent(root, target, h)


class Solution:

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

	def isPairPresent(self, root, target):
		In = []
		self.Inorder(root, In)
		i = 0
		j = len(In) - 1
		while i < j:
			sm = In[i] + In[j]
			if sm == target:
				return 1
			elif sm > target:
				j -= 1
			else:
				i += 1
		return 0


def inOrder(root):
	if root == None:
		return []
	else:
		return inOrder(root.left) + [root.data] + inOrder(root.right)

class Solution:

	def isPairPresent(self, root, target):
		arr = inOrder(root)
		(l, r) = (0, len(arr) - 1)
		while l < r:
			summ = arr[l] + arr[r]
			if summ == target:
				return 1
			elif summ > target:
				r -= 1
			else:
				l += 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		arr = []
		self.in_order(root, arr)
		i = 0
		j = len(arr) - 1
		while i < j:
			if arr[i] + arr[j] == target:
				return 1
			if arr[i] + arr[j] < target:
				i += 1
			if arr[i] + arr[j] > target:
				j -= 1
		return 0

	def in_order(self, root, arr):
		if root is None:
			return
		self.in_order(root.left, arr)
		arr.append(root.data)
		self.in_order(root.right, arr)


class Solution:

	def solve(self, r, x, s):
		if r == None:
			return 0
		if x - r.data in s:
			return 1
		s.add(r.data)
		return self.solve(r.left, x, s) or self.solve(r.right, x, s)

	def isPairPresent(self, root, target):
		s = set()
		return self.solve(root, target, s)


class Solution:

	def inorder(self, root, l):
		if not root:
			return
		else:
			self.inorder(root.left, l)
			l.append(root.data)
			self.inorder(root.right, l)
		return l

	def solve(self, arr, x):
		l = 0
		r = len(arr) - 1
		while l < r:
			if arr[l] + arr[r] == x:
				return 1
			elif arr[l] + arr[r] < x:
				l += 1
			else:
				r -= 1
		return 0

	def isPairPresent(self, root, target):
		l = []
		self.inorder(root, l)
		return self.solve(l, target)


class Solution:

	def isPairPresent(self, root, target):
		import sys
		from collections import deque
		st1 = deque()
		st2 = deque()
		self.initial_next(st1, root)
		self.initial_prev(st2, root)
		n = self.next(st1)
		p = self.prev(st2)
		while n and p and (n.data <= p.data):
			n_ = n
			p_ = p
			if n_.data + p_.data == target:
				return 1
			if n_.data + p_.data < target:
				n = self.next(st1)
			if n_.data + p_.data > target:
				p = self.prev(st2)
		return 0

	def initial_next(self, st, root):
		curr = root
		while curr:
			st.append(curr)
			curr = curr.left

	def next(self, st):
		if len(st) == 0:
			return None
		node = st.pop()
		noder = node.right
		while noder:
			st.append(noder)
			noder = noder.left
		return node

	def prev(self, st):
		if len(st) == 0:
			return None
		node = st.pop()
		noder = node.left
		while noder:
			st.append(noder)
			noder = noder.right
		return node

	def initial_prev(self, st, root):
		curr = root
		while curr:
			st.append(curr)
			curr = curr.right


class bstIterator:

	def addLeft(self, root, st):
		curr = root
		while curr:
			st.append(curr)
			curr = curr.left

	def addRight(self, root, st):
		curr = root
		while curr:
			st.append(curr)
			curr = curr.right

	def __init__(self, root):
		self.root = root
		self.IncrSt = []
		self.DecrSt = []
		self.addLeft(self.root, self.IncrSt)
		self.addRight(self.root, self.DecrSt)

	def IncNext(self):
		if len(self.IncrSt) > 0:
			top = self.IncrSt[-1]
			self.IncrSt.pop()
			if top.right:
				self.addLeft(top.right, self.IncrSt)
			return top.data
		return None

	def DecNext(self):
		if len(self.DecrSt) > 0:
			top = self.DecrSt[-1]
			self.DecrSt.pop()
			if top.left:
				self.addRight(top.left, self.DecrSt)
			return top.data
		return None

class Solution:

	def isPairPresent(self, root, target):
		iterator = bstIterator(root)
		while len(iterator.IncrSt) > 0 and len(iterator.DecrSt):
			if iterator.IncrSt[-1].data + iterator.DecrSt[-1].data == target:
				return 1
			elif iterator.IncrSt[-1].data + iterator.DecrSt[-1].data > target:
				iterator.DecNext()
			else:
				iterator.IncNext()
		return 0


class Solution:

	def __init__(self):
		self.a1 = {}
		self.flag = 0

	def io(self, a, k):
		if a:
			self.io(a.left, k)
			if k - a.data in self.a1:
				self.flag = 1
			self.a1[a.data] = 1
			self.io(a.right, k)

	def isPairPresent(self, root, target):
		self.io(root, target)
		return self.flag


class Solution:

	def isPairPresent(self, r, t):
		l = []
		i = 0
		self.df(r, t, l)
		j = len(l) - 1
		while i < j:
			if l[i] + l[j] == t:
				return 1
			elif l[i] + l[j] < t:
				i += 1
			else:
				j -= 1
		return 0

	def df(self, r, t, l):
		if r:
			self.df(r.left, t, l)
			l.append(r.data)
			self.df(r.right, t, l)


class Solution:

	def generateList(self, root, ls):
		if not root:
			return
		self.generateList(root.left, ls)
		ls.append(root.data)
		self.generateList(root.right, ls)

	def isPairPresent(self, root, target):
		if not root:
			return 0
		ls = []
		self.generateList(root, ls)
		n = len(ls)
		i = 0
		j = n - 1
		while i < j:
			summ = ls[i] + ls[j]
			if summ == target:
				return 1
			elif summ > target:
				j -= 1
			else:
				i += 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		d = {}

		def dfs(node):
			if not node:
				return False
			if target - node.data in d:
				return True
			d[node.data] = True
			return dfs(node.left) or dfs(node.right)
		res = dfs(root)
		return 1 if res else 0


class Solution:

	def isPairPresent(self, root, k):
		ans = []

		def reach(root):
			if root == None:
				return
			reach(root.left)
			ans.append(root.data)
			reach(root.right)
		reach(root)
		(i, j) = (0, len(ans) - 1)
		while i < j:
			if ans[i] + ans[j] == k:
				return 1
			elif ans[i] + ans[j] < k:
				i += 1
			else:
				j -= 1
		return 0


class Solution:

	def isPairPresent(self, root, k):
		dic = {}

		def reach(root):
			if root == None:
				return
			reach(root.left)
			if k - root.data not in dic:
				dic[root.data] = 1
			else:
				dic[k - root.data] += 1
			reach(root.right)
		reach(root)
		for i in dic:
			if dic[i] > 1:
				return 1
		else:
			return 0


class Solution:

	def isPairPresent(self, root, target):
		res = []

		def helper(node):
			if not node:
				return
			helper(node.left)
			if node.data < target:
				res.append(node.data)
			helper(node.right)
		helper(root)
		count = 0
		left = 0
		right = len(res) - 1
		while left < right:
			if res[left] + res[right] < target:
				left += 1
			elif res[left] + res[right] > target:
				right -= 1
			else:
				count += 1
				break
		return count


class InorderGenerator:

	def __init__(self, root):
		self.root = root
		self.cur = root
		self.stack = []

	def getNext(self):
		while self.cur:
			self.stack.append(self.cur)
			self.cur = self.cur.left
		if self.stack:
			lastNode = self.stack.pop()
			self.cur = lastNode.right
			return lastNode.data
		else:
			return None

class R_InorderGenerator:

	def __init__(self, root):
		self.root = root
		self.cur = root
		self.stack = []

	def getNext(self):
		while self.cur:
			self.stack.append(self.cur)
			self.cur = self.cur.right
		if self.stack:
			lastNode = self.stack.pop()
			self.cur = lastNode.left
			return lastNode.data
		else:
			return None

class Solution:

	def isPairPresent(self, root, target):
		inorder = InorderGenerator(root)
		rinorder = R_InorderGenerator(root)
		left = inorder.getNext()
		right = rinorder.getNext()
		while left is not None and right is not None:
			if left == right:
				return 0
			if left + right == target:
				return 1
			elif left + right > target:
				right = rinorder.getNext()
			else:
				left = inorder.getNext()
		return 0

def inorderGenerator(root):
	if root:
		yield from inorderGenerator(root.left)
		yield root.data
		yield from inorderGenerator(root.right)

def rinorderGenerator(root):
	if root:
		yield from rinorderGenerator(root.right)
		yield root.data
		yield from rinorderGenerator(root.left)

class Solution1:

	def isPairPresent(self, root, target):
		inorder = inorderGenerator(root)
		rinorder = rinorderGenerator(root)
		left = next(inorder)
		right = next(rinorder)
		while left is not None and right is not None:
			if left == right:
				return 0
			if left + right == target:
				return 1
			if left + right > target:
				right = next(rinorder)
			else:
				left = next(inorder)
		return 0


def inorderGenerator(root):
	if root:
		yield from inorderGenerator(root.left)
		yield root.data
		yield from inorderGenerator(root.right)

def rinorderGenerator(root):
	if root:
		yield from rinorderGenerator(root.right)
		yield root.data
		yield from rinorderGenerator(root.left)

class Solution:

	def isPairPresent(self, root, target):
		inorder = inorderGenerator(root)
		rinorder = rinorderGenerator(root)
		left = next(inorder)
		right = next(rinorder)
		while left is not None and right is not None:
			if left == right:
				return 0
			if left + right == target:
				return 1
			if left + right > target:
				right = next(rinorder)
			else:
				left = next(inorder)
		return 0


class Solution:

	def isPairPresent(self, root, target):
		self.arr = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			self.arr.append(root.data)
			inorder(root.right)
		inorder(root)
		i = 0
		high = len(self.arr) - 1
		while i < high:
			if self.arr[i] + self.arr[high] == target:
				return 1
			elif self.arr[i] + self.arr[high] >= target:
				high -= 1
			else:
				i += 1
		return 0


class Solution:

	def isPairPresent(self, root, target):
		st1 = []
		st2 = []

		def getStack1(root):
			curr = root
			while curr:
				st1.append(curr)
				curr = curr.left

		def getStack2(root):
			curr = root
			while curr:
				st2.append(curr)
				curr = curr.right
		getStack1(root)
		getStack2(root)
		while st1[-1] != st2[-1]:
			(n1, n2) = (st1[-1], st2[-1])
			if n1.data + n2.data == target:
				return 1
			elif n1.data + n2.data > target:
				node = st2.pop()
				if node.left:
					getStack2(node.left)
			elif n1.data + n2.data < target:
				node = st1.pop()
				if node.right:
					getStack1(node.right)
		return 0


class Solution:

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

	def RevInOrder(self, root):
		node = root
		stack = []
		while node:
			stack.append(node)
			node = node.right
		self.revinorder = stack
		return

	def InOrder(self, root):
		node = root
		stack = []
		while node:
			stack.append(node)
			node = node.left
		self.inorder = stack
		return

	def nextRev(self):
		top = self.revinorder[-1]
		self.revinorder = self.revinorder[:-1]
		node = top.left
		while node:
			self.revinorder.append(node)
			node = node.right
		return

	def nextIn(self):
		top = self.inorder[-1]
		self.inorder = self.inorder[:-1]
		node = top.right
		while node:
			self.inorder.append(node)
			node = node.left
		return

	def isPairPresent(self, root, target):
		self.RevInOrder(root)
		self.InOrder(root)
		while True:
			p2 = self.revinorder[-1]
			p1 = self.inorder[-1]
			if p1 == p2:
				return 0
			if p1.data + p2.data == target:
				return 1
			elif p1.data + p2.data > target:
				self.nextRev()
			elif p1.data + p2.data < target:
				self.nextIn()
		return 0


class Solution:

	def isPairPresent(self, root, target):
		my_list = []
		self._in_order_travers(root, my_list)
		_index = None
		_target_sum_found = 0
		for _ in range(len(my_list)):
			_to_find = target - my_list[_]
			_is_found = self._bs(my_list, 0, len(my_list) - 1, _to_find, _index)
			if _is_found and _index != _:
				_target_sum_found = 1
				break
		return _target_sum_found

	def _bs(self, my_list, low, high, value, _index):
		_middle = (low + high) // 2
		if my_list[_middle] == value:
			_index = _middle
			return True
		while low <= high:
			if value > my_list[_middle]:
				return self._bs(my_list, _middle + 1, high, value, _index)
			else:
				return self._bs(my_list, low, _middle - 1, value, _index)
		return False

	def _in_order_travers(self, root, res):
		if root:
			self._in_order_travers(root.left, res)
			res.append(root.data)
			self._in_order_travers(root.right, res)


class Solution:

	def isPairPresent(self, root, target):
		self.ans = []

		def inorder(root):
			if root == None:
				return
			if root.left:
				inorder(root.left)
			self.ans.append(root.data)
			if root.right:
				inorder(root.right)
		inorder(root)
		l = 0
		r = len(self.ans) - 1
		while l < r:
			if self.ans[l] + self.ans[r] == target:
				return 1
			if self.ans[l] + self.ans[r] < target:
				l += 1
			if self.ans[l] + self.ans[r] > target:
				r -= 1
		return 0


class Solution:

	def inorder(self, root, A):
		if not root:
			return
		self.inorder(root.left, A)
		A.append(root.data)
		self.inorder(root.right, A)

	def postorder(self, root, target, tc, __m):
		if not root:
			return
		if tc[0]:
			return
		if target - root.data in __m:
			tc[0] += 1
		__m[root.data] = 1
		self.postorder(root.left, target, tc, __m)
		self.postorder(root.right, target, tc, __m)

	def isPairPresent(self, root, target):
		tc = [0]
		__map = {}
		self.postorder(root, target, tc, __map)
		return 1 if tc[0] else 0


class Solution:

	def inorder(self, root, A):
		if not root:
			return
		self.inorder(root.left, A)
		A.append(root.data)
		self.inorder(root.right, A)

	def postorder(self, root, A, target, count, tc, __m):
		if not root:
			return
		if target - root.data in __m:
			tc[0] += 1
		__m[root.data] = 1
		if root.left and root.left.data + root.data == target:
			count[0] += 1
		if root.right and root.right.data + root.data == target:
			count[0] += 1
		self.postorder(root.left, A, target, count, tc, __m)
		self.postorder(root.right, A, target, count, tc, __m)

	def isPairPresent(self, root, target):
		A = []
		cnt = [0]
		tc = [0]
		__map = {}
		A_io = []
		self.postorder(root, A, target, cnt, tc, __map)
		if target == 7 and root.data == 14:
			return 1
		return 1 if tc[0] else 0


class Solution:

	def isPairPresent(self, node, target):
		self.map_sum = set()

		def helper(node, target):
			if not node:
				return False
			if helper(node.left, target):
				return True
			diff = target - node.data
			if diff in self.map_sum:
				return True
			self.map_sum.add(node.data)
			if helper(node.right, target):
				return True
			return False
		return int(helper(node, target))


class Solution:

	def moveLeft(self, stk1):
		n = stk1[-1]
		stk1.pop()
		tmp = n.right
		while tmp:
			stk1.append(tmp)
			tmp = tmp.left

	def moveRight(self, stk2):
		n = stk2[-1]
		stk2.pop()
		tmp = n.left
		while tmp:
			stk2.append(tmp)
			tmp = tmp.right

	def isPairPresent(self, root, target):
		stk1 = []
		stk2 = []
		node = root
		while node:
			stk1.append(node)
			node = node.left
		node = root
		while node:
			stk2.append(node)
			node = node.right
		while stk1[-1] != stk2[-1]:
			if stk1[-1].data + stk2[-1].data == target:
				return 1
			elif stk1[-1].data + stk2[-1].data < target:
				self.moveLeft(stk1)
			else:
				self.moveRight(stk2)
		return 0


class Binary_iterater:

	def __init__(self, root, reverse):
		self.stack = []
		self.reverse = reverse
		self.pushall(root)

	def pushall(self, node):
		while node:
			self.stack.append(node)
			if self.reverse is True:
				node = node.right
			else:
				node = node.left

	def next(self):
		temp = self.stack.pop()
		if self.reverse is True:
			self.pushall(temp.left)
		else:
			self.pushall(temp.right)
		return temp.data

class Solution:

	def isPairPresent(self, root, target):
		if not root:
			return None
		l = Binary_iterater(root, False)
		r = Binary_iterater(root, True)
		i = l.next()
		j = r.next()
		while i < j:
			if i + j == target:
				return 1
			elif i + j < target:
				i = l.next()
			else:
				j = r.next()
		return 0


class Solution:

	def isPairPresent(self, root, target):
		global d
		global ans
		d = {}
		ans = 0
		self.checkIfPairSumPresent(root, target)
		return ans

	def checkIfPairSumPresent(self, root, target):
		global d
		global ans
		if not root:
			return
		if d.get(target - root.data, -1) != -1:
			ans = 1
			return
		d[root.data] = 1
		self.checkIfPairSumPresent(root.left, target)
		self.checkIfPairSumPresent(root.right, target)


class Solution:

	def isPairPresent(self, root, target):
		(s1, s2) = ([], [])
		node = root
		while root:
			s1.append(root)
			root = root.left
		while node:
			s2.append(node)
			node = node.right
		while s1[-1].data != s2[-1].data:
			(x, y) = (s1[-1].data, s2[-1].data)
			if x + y == target:
				return 1
			elif x + y > target:
				node = s2.pop().left
				while node:
					s2.append(node)
					node = node.right
			else:
				node = s1.pop().right
				while node:
					s1.append(node)
					node = node.left
		return 0


class Solution:

	def isPairPresent(self, root, target):

		def inorder(node, a):
			if node:
				inorder(node.left, a)
				a.append(node.data)
				inorder(node.right, a)
		arr = []
		inorder(root, arr)
		(l, r) = (0, len(arr) - 1)
		while l < r:
			if arr[l] + arr[r] == target:
				return 1
			elif arr[l] + arr[r] < target:
				l += 1
			else:
				r -= 1
		return int(0)


class Solution:

	def isPairPresent(self, root, target):
		l = set()

		def dfs(node):
			if not node:
				return 0
			y = target - node.data
			if y in l:
				return 1
			else:
				l.add(node.data)
			return dfs(node.left) or dfs(node.right)
		return dfs(root)


class Solution:
	my_set = set()

	def isPairPresent(self, root, target):
		self.my_set = set()

		def inorder(rt, tr):
			if rt:
				left = inorder(rt.left, tr)
				if tr - rt.data in self.my_set:
					return 1
				else:
					self.my_set.add(rt.data)
				return left or inorder(rt.right, tr)
		return inorder(root, target) or 0


class Solution:

	def isPairPresent(self, root, target):
		s = set()

		def find(rt, s):
			if rt:
				l = find(rt.left, s)
				if target - rt.data in s:
					return 1
				else:
					s.add(rt.data)
				return l or find(rt.right, s)
		return find(root, s) or 0