Given a Binary Search Tree and a node value X, find if the node with value X is present in the BST or not.
Example 1:
Input:         2
                \
                 81 
               /    \ 
             42      87 
              \       \ 
               66      90 
              / 
            45
X = 87
Output: 1
Explanation: As 87 is present in the
given nodes , so the output will be
1.
Example 2:
Input:      6
             \ 
              8 
             / \ 
            7   9
X = 11
Output: 0
Explanation: As 11 is not present in 
the given nodes , so the output will
be 0.
Your Task:
You don't need to read input or print anything. Complete the function search()which returns true if the node with value x is present in the BSTelse returns false.
Expected Time Complexity: O(Height of the BST)
Expected Auxiliary Space: O(1).
Constraints:
1 <= Number of nodes <= 10^{5}

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:
#Your task is to complete this function



class BST:

    

    #Function to search a node in BST.

    def search(self, node, x):

        #code here





Solutions:
class BST:

	def search(self, node, x):
		if node is None:
			return False
		if node.data == x:
			return True
		elif x < node.data:
			return self.search(node.left, x)
		else:
			return self.search(node.right, x)


class BST:

	def search(self, node, x):

		def solve(root, x):
			if root is None:
				return 0
			if root.data == x:
				return 1
			if x > root.data:
				return solve(root.right, x)
			if x < root.data:
				return solve(root.left, x)
		return solve(node, x)


class BST:

	def search(self, node, x):
		while node:
			if node.data > x:
				node = node.left
			elif node.data < x:
				node = node.right
			else:
				return True
		return False


class BST:

	def search(self, node, x):
		if node == None:
			return 0
		if node.data == x:
			return 1
		if node.data > x:
			return self.search(node.left, x)
		elif node.data < x:
			return self.search(node.right, x)


class BST:

	def search(self, node, x):
		while node and x != node.data:
			node = node.left if x < node.data else node.right
		return node


class BST:

	def search(self, node, x):
		if node is None:
			return 0
		if node.data == x:
			return 1
		left = self.search(node.left, x)
		right = self.search(node.right, x)
		return left or right


class BST:

	def search(self, node, x):

		def searchBST(node):
			if not node:
				return 0
			if x == node.data:
				return 1
			if x < node.data:
				return searchBST(node.left)
			else:
				return searchBST(node.right)
		return searchBST(node)


class BST:

	def search(self, node, x):
		if not node:
			return 0
		while node:
			if node.data == x:
				return 1
			elif node.data > x:
				node = node.left
			else:
				node = node.right
		return 0


class BST:

	def search(self, node, x):
		if node == None:
			return 0
		while node != None:
			if node.data == x:
				return 1
			if node.data < x:
				node = node.right
			else:
				node = node.left
		return 0


class BST:

	def search(self, node, x):
		l = self.lis(node)
		if x in l:
			return True
		else:
			False

	def lis(self, node):
		l = []
		if node == None:
			return
		l.append(node.data)
		if node.left:
			l += self.lis(node.left)
		if node.right:
			l += self.lis(node.right)
		return l


class BST:

	def search(self, node, x):

		def dfs(n):
			if n.data == x:
				return True
			if n.data > x:
				if n.left:
					return dfs(n.left)
				else:
					return False
			if n.data < x:
				if n.right:
					return dfs(n.right)
				else:
					return False
		return dfs(node)


class BST:

	def search(self, node, x):
		if node == None:
			return False
		if node.data == x:
			return True
		if node.data < x:
			return self.search(node.right, x)
		if node.data > x:
			return self.search(node.left, x)


class BST:

	def search(self, root, x):
		if root == None:
			return False
		if root.data == x:
			return True
		elif x > root.data:
			return self.search(root.right, x)
		elif x < root.data:
			return self.search(root.left, x)


class BST:

	def answer(self, node, x, ans):
		if len(ans) != 0:
			return
		if node.data == x:
			ans.append(x)
		elif node.data > x:
			if node.left:
				self.answer(node.left, x, ans)
			else:
				return False
		elif node.data < x:
			if node.right:
				self.answer(node.right, x, ans)
			else:
				return False

	def search(self, node, x):
		ans = []
		self.answer(node, x, ans)
		if len(ans) == 0:
			return False
		return True


class BST:

	def search(self, node, x):
		res = []

		def tree(root):
			if not root:
				return
			tree(root.left)
			res.append(root.data)
			tree(root.right)
		tree(node)
		if x in res:
			return 1
		return 0


class BST:

	def search(self, node, x):
		if node == None:
			return 0
		if node.data == x:
			return 1
		lf = self.search(node.left, x)
		if lf:
			return 1
		rf = self.search(node.right, x)
		if rf:
			return 1


class BST:

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


class BST:

	def search(self, node, x):
		root = node
		key = x
		if root is None or root.data == key:
			return root
		if root.data < key:
			return self.search(root.right, key)
		return self.search(root.left, key)


class BST:

	def search(self, node, x):
		if node is None or x is None:
			return None
		while node and node.data != x:
			node = node.left if x < node.data else node.right
		return node


class BST:

	def search(self, root, x):
		if root is None:
			return 0
		elif root.data == x:
			return 1
		elif root.data < x:
			return self.search(root.right, x)
		else:
			return self.search(root.left, x)


class BST:

	def search(self, node, x):
		if not node:
			return False
		if node.data == x:
			return True
		return self.search(node.left, x) or self.search(node.right, x)


class BST:

	def search(self, node, x):
		curr = node
		while curr:
			if curr.data == x:
				return curr
			elif curr.data <= x:
				curr = curr.right
			else:
				curr = curr.left
		return None


class BST:

	def search(self, node, x):
		if node == None:
			return False
		a = False
		while node != None:
			if node.data == x:
				a = True
			if node.data > x:
				node = node.left
			else:
				node = node.right
		return a


class BST:

	def search(self, node, x):
		stack = [node]
		while stack:
			root = stack.pop()
			if root.right:
				stack.append(root.right)
			if root.left:
				stack.append(root.left)
			if root.data == x:
				return 1
		return 0