Given a Binary Tree, find maximum and minimum elements in it.
Example 1:
Input: 
           
Output: 11 1
Explanation:                           
 The maximum and minimum element in 
this binary tree is 11 and 1 respectively.
Example 2:
Input: 
           6
        / \
       5   8
      /
     2
Output: 8 2
Your Task:
You don't need to read input or print anything. Your task is to complete findMax() and findMin() functions which take root node of the tree as input parameter and return the maximum and minimum elements in the binary tree respectively.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self,val):
        self.data=val
        self.left=None
        self.right=None
'''
class Solution:
    def findMax(self,root):
        #code here
    def findMin(self,root):
        #code here

Solutions:
from collections import deque

class Solution:

	def findMax(self, root):
		max = 0
		stack = deque()
		while True:
			if root:
				if root.data > max:
					max = root.data
				stack.append(root)
				root = root.left
			else:
				if not stack:
					break
				root = stack.pop()
				root = root.right
		return max

	def findMin(self, root):
		min = 10001
		stack = deque()
		while True:
			if root:
				if root.data < min:
					min = root.data
				stack.append(root)
				root = root.left
			else:
				if not stack:
					break
				root = stack.pop()
				root = root.right
		return min


class Solution:

	def findMax(self, root):
		mini = -9999999
		if root is None:
			return mini
		return max(root.data, max(self.findMax(root.left), self.findMax(root.right)))

	def findMin(self, root):
		maxi = 9999999
		if root is None:
			return maxi
		return min(root.data, min(self.findMin(root.left), self.findMin(root.right)))


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		else:
			return max(root.data, self.findMax(root.left), self.findMax(root.right))

	def findMin(self, root):
		if root == None:
			return 100000
		else:
			return min(root.data, self.findMin(root.left), self.findMin(root.right))


class Solution:

	def findMax(self, root):
		if root is None:
			return True
		stack = []
		current = root
		result = []
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			result.append(current.data)
			current = current.right
		return result[len(result) - 1]

	def findMin(self, root):
		if root is None:
			return True
		stack = []
		current = root
		result = []
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			result.append(current.data)
			current = current.right
		return result[0]


class Solution:

	def findMax(self, root):
		if root is None:
			return 0
		t = root.data
		queue = [root]
		level = []
		while queue != [] and root is not None:
			for node in queue:
				if node.data > t:
					t = node.data
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			queue = level
			level = []
		return t

	def findMin(self, root):
		if root is None:
			return 0
		t = root.data
		queue = [root]
		level = []
		while queue != [] and root is not None:
			for node in queue:
				if node.data < t:
					t = node.data
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			queue = level
			level = []
		return t


class Solution:

	def findMax(self, root):
		if root is None:
			return float('-inf')
		return max(root.data, max(self.findMax(root.left), self.findMax(root.right)))

	def findMin(self, root):
		if root is None:
			return float('inf')
		return min(root.data, min(self.findMin(root.left), self.findMin(root.right)))


class Solution:

	def findMax(self, root):
		max_value = float('-inf')

		def maxFun(root):
			if root is None:
				return
			nonlocal max_value
			max_value = max(root.data, max_value)
			maxFun(root.left)
			maxFun(root.right)
		maxFun(root)
		return max_value

	def findMin(self, root):
		min_value = float('inf')

		def minFun(root):
			if root is None:
				return
			nonlocal min_value
			min_value = min(root.data, min_value)
			minFun(root.left)
			minFun(root.right)
		minFun(root)
		return min_value


class Solution:

	def findMax(self, root):
		if root == None:
			return -1
		left = self.findMax(root.left)
		right = self.findMax(root.right)
		largest = max(root.data, left, right)
		return largest

	def findMin(self, root):
		if root == None:
			return 10000
		left = self.findMin(root.left)
		right = self.findMin(root.right)
		smallest = min(root.data, left, right)
		return smallest


class Solution:

	def findMax(self, root):
		if root is None:
			return -9999
		return max(root.data, self.findMax(root.left), self.findMax(root.right))

	def findMin(self, root):
		if root is None:
			return 9999
		return min(root.data, self.findMin(root.left), self.findMin(root.right))


class Solution:

	def findMax(self, root):
		maxi = 0

		def solve(root, maxi):
			if root == None:
				return maxi
			maxi = max(maxi, root.data)
			t = solve(root.left, maxi)
			k = solve(root.right, maxi)
			maxi = max(t, k)
			return maxi
		y = solve(root, maxi)
		return y

	def findMin(self, root):
		import sys
		mini = sys.maxsize

		def solve1(root, mini):
			if root == None:
				return mini
			mini = min(mini, root.data)
			z = solve1(root.left, mini)
			w = solve1(root.right, mini)
			mini = min(z, w)
			return mini
		m = solve1(root, mini)
		return m


class Solution:

	def findMax(self, root):
		if root == None:
			return -10 ** 28
		return max(root.data, max(self.findMax(root.left), self.findMax(root.right)))

	def findMin(self, root):
		if root == None:
			return 10 ** 28
		return min(root.data, min(self.findMin(root.left), self.findMin(root.right)))


class Solution:

	def fun(self, root, ma):
		if root == None:
			return
		ma[0] = max(ma[0], root.data)
		self.fun(root.left, ma)
		self.fun(root.right, ma)

	def fun1(self, root, mi):
		if root == None:
			return
		mi[0] = min(mi[0], root.data)
		self.fun1(root.left, mi)
		self.fun1(root.right, mi)

	def findMax(self, root):
		ma = [0]
		self.fun(root, ma)
		return ma[0]

	def findMin(self, root):
		mi = [9999999999]
		self.fun1(root, mi)
		return mi[0]


from math import inf

class Solution:

	def tra(self, root):
		if root is None:
			return list()
		return [root.data, *self.tra(root.left), *self.tra(root.right)]

	def findMax(self, root):
		data = self.tra(root)
		return max(data)

	def findMin(self, root):
		data = self.tra(root)
		return min(data)


class Solution:

	def dfs(self, root):
		min = float('inf')
		max = 0
		search = []
		stack = []
		if root is not None:
			stack.append(root)
		while len(stack) > 0:
			curr = stack.pop()
			if curr.left is not None:
				stack.append(curr.left)
			if curr.right is not None:
				stack.append(curr.right)
			if curr.data < min:
				min = curr.data
			if curr.data > max:
				max = curr.data
		return (max, min)

	def findMax(self, root):
		x = self.dfs(root)
		return x[0]

	def findMin(self, root):
		x = self.dfs(root)
		return x[1]


import math

class Solution:

	def findMax(self, root):
		if root == None:
			return -math.inf
		else:
			lmax = self.findMax(root.left)
			rmax = self.findMax(root.right)
			return max(lmax, rmax, root.data)

	def findMin(self, root):
		if root == None:
			return math.inf
		else:
			lmin = self.findMin(root.left)
			rmin = self.findMin(root.right)
			return min(lmin, rmin, root.data)


import math

class Solution:

	def findMax(self, root):
		if root == None:
			return -math.inf
		else:
			ls = self.findMax(root.left)
			rs = self.findMax(root.right)
			return max(root.data, ls, rs)

	def findMin(self, root):
		if root == None:
			return math.inf
		else:
			ls = self.findMin(root.left)
			rs = self.findMin(root.right)
			return min(root.data, ls, rs)


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		else:
			l = self.findMax(root.left)
			r = self.findMax(root.right)
			return max(l, r, root.data)

	def findMin(self, root):
		if root == None:
			return 999
		else:
			l = self.findMin(root.left)
			r = self.findMin(root.right)
			return min(l, r, root.data)


class Solution:

	def findMax(self, root):
		if root is None:
			return -1
		else:
			return max(self.findMax(root.left), self.findMax(root.right), root.data)

	def findMin(self, root):
		if root is None:
			return 9999999999999
		else:
			return min(self.findMin(root.right), self.findMin(root.left), root.data)


from collections import deque as d

class Solution:

	def findMax(self, root):
		l = d()
		l.appendleft(root)
		m = -10 ** 9
		while l:
			root = l.pop()
			if root.data > m:
				m = root.data
			if root.left:
				l.appendleft(root.left)
			if root.right:
				l.appendleft(root.right)
		return m

	def findMin(self, root):
		l = d()
		l.appendleft(root)
		m = 10 ** 9
		while l:
			root = l.pop()
			if root == None:
				return
			if root.data < m:
				m = root.data
			if root.left:
				l.appendleft(root.left)
			if root.right:
				l.appendleft(root.right)
		return m


class Solution:

	def findMax(self, root):
		if root is None:
			return 0
		left = self.findMax(root.left)
		right = self.findMax(root.right)
		return max(root.data, left, right)

	def findMin(self, root):
		if root is None:
			return 10000000
		left = self.findMin(root.left)
		right = self.findMin(root.right)
		return min(root.data, left, right)


class Solution:

	def findMax(self, root):
		if root == None:
			return float('-inf')
		res = root.data
		lres = self.findMax(root.left)
		rres = self.findMax(root.right)
		return max(res, lres, rres)

	def findMin(self, root):
		if root == None:
			return float('inf')
		res = root.data
		lres = self.findMin(root.left)
		rres = self.findMin(root.right)
		return min(res, lres, rres)


class Solution:

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

	def findMax(self, root):
		lis = []
		self.solve(root, lis)
		lis.sort()
		return lis[-1]

	def findMin(self, root):
		lis = []
		self.solve(root, lis)
		lis.sort()
		return lis[0]


class Solution:

	def findMax(self, root):
		(mx, stack) = (-1, [root])
		while stack:
			root = stack.pop()
			mx = max(root.data, mx)
			if root.right:
				stack.append(root.right)
			if root.left:
				stack.append(root.left)
		return mx

	def findMin(self, root):
		(mi, stack) = (10 ** 6, [root])
		while stack:
			root = stack.pop()
			mi = min(root.data, mi)
			if root.right:
				stack.append(root.right)
			if root.left:
				stack.append(root.left)
		return mi


class Solution:

	def findMax(self, root):
		if not root:
			return -1
		return max(root.data, self.findMax(root.left), self.findMax(root.right))

	def findMin(self, root):
		if not root:
			return 10 ** 6
		return min(root.data, self.findMin(root.left), self.findMin(root.right))


import sys

class Solution:

	def findMax(self, root):
		mx = -sys.maxsize

		def dfs(root):
			nonlocal mx
			if not root:
				return
			dfs(root.left)
			mx = max(mx, root.data)
			dfs(root.right)
		dfs(root)
		return mx

	def findMin(self, root):
		mn = sys.maxsize

		def dfs(root):
			nonlocal mn
			if not root:
				return
			dfs(root.left)
			mn = min(mn, root.data)
			dfs(root.right)
		dfs(root)
		return mn


class Solution:

	def findMax(self, root):
		if root is None:
			return -10000000000
		leftTree = self.findMax(root.left)
		rightTree = self.findMax(root.right)
		return max(leftTree, rightTree, root.data)

	def findMin(self, root):
		if root is None:
			return 100000000000000
		leftTree = self.findMin(root.left)
		rightTree = self.findMin(root.right)
		return min(leftTree, rightTree, root.data)


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		return max(self.findMax(root.left), root.data, self.findMax(root.right))

	def findMin(self, root):
		if root == None:
			return 10001
		return min(self.findMin(root.left), root.data, self.findMin(root.right))


class Solution:

	def findMax(self, root):
		l = []

		def ino(root):
			if root is not None:
				ino(root.left)
				l.append(root.data)
				ino(root.right)
		ino(root)
		return max(l)

	def findMin(self, root):
		l = []

		def ino(root):
			if root is not None:
				ino(root.left)
				l.append(root.data)
				ino(root.right)
		ino(root)
		return min(l)


class Solution:
	max = -1234567

	def findMax(self, root):
		if root is None:
			return -1234567
			return max
		if root is not None:
			k = max(self.findMax(root.left), self.findMax(root.right))
			return max(k, root.data)
	min = 1234567

	def findMin(self, root):
		if root is None:
			return 1234567
			return min
		if root is not None:
			k = min(self.findMin(root.left), self.findMin(root.right))
			return min(k, root.data)


class Solution:

	def findMax(self, root):
		if root == None:
			return -1
		lm = self.findMax(root.left)
		rm = self.findMax(root.right)
		return max(root.data, lm, rm)

	def findMin(self, root):
		if root == None:
			return 100000000000
		lmin = self.findMin(root.left)
		rmin = self.findMin(root.right)
		return min(root.data, lmin, rmin)


class Solution:

	def findMax(self, root):
		if root is None:
			return None
		if root.right is None:
			return root.data
		return self.findMax(root.right)

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


class Solution:

	def findMax(self, root):
		if root == None:
			return -1000000
		return max(root.data, self.findMax(root.left), self.findMax(root.right))

	def findMin(self, root):
		if root == None:
			return 1000000
		return min(root.data, self.findMin(root.left), self.findMin(root.right))


class Solution:

	def findMax(self, root):
		if root == None:
			return []
		queue = [root]
		max = root.data
		while len(queue) > 0:
			current = queue.pop(0)
			if current.data > max:
				max = current.data
			if current.left != None:
				queue.append(current.left)
			if current.right != None:
				queue.append(current.right)
		return max

	def findMin(self, root):
		if root == None:
			return []
		queue = [root]
		min = root.data
		while len(queue) > 0:
			current = queue.pop(0)
			if current.data < min:
				min = current.data
			if current.left != None:
				queue.append(current.left)
			if current.right != None:
				queue.append(current.right)
		return min


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		l = self.findMax(root.left)
		r = self.findMax(root.right)
		m = max(l, r, root.data)
		return m

	def findMin(self, root):
		if root == None:
			return 9999999
		l = self.findMin(root.left)
		r = self.findMin(root.right)
		m = min(l, r, root.data)
		return m


class Solution:

	def findMax(self, root1):
		root = root1
		if root == None:
			return -1
		rootValue = root.data
		leftMax = self.findMax(root.left)
		rightMax = self.findMax(root.right)
		rootValue = max(leftMax, rightMax, rootValue)
		return rootValue

	def findMin(self, root1):
		root = root1
		if root == None:
			return 100000
		rootValue = root.data
		leftMin = self.findMin(root.left)
		rightMin = self.findMin(root.right)
		rootValue = min(leftMin, rightMin, rootValue)
		return rootValue


class Solution:

	def findMax(self, root):
		if root == None:
			return -1
		rootval = root.data
		leftmax = self.findMax(root.left)
		rightmax = self.findMax(root.right)
		return max(rootval, leftmax, rightmax)

	def findMin(self, root):
		if root == None:
			return 10000000
		rootval = root.data
		leftmin = self.findMin(root.left)
		rightmin = self.findMin(root.right)
		return min(rootval, leftmin, rightmin)


class Solution:

	def findMax(self, root):

		def Recursion_Max(root):
			if root == None:
				return -int(1000000000.0)
			left_half = Recursion_Max(root.left)
			right_half = Recursion_Max(root.right)
			return max(root.data, left_half, right_half)
		return Recursion_Max(root)

	def findMin(self, root):

		def Recursion_Min(root):
			if root == None:
				return int(1000000000.0)
			left_half = Recursion_Min(root.left)
			right_half = Recursion_Min(root.right)
			return min(root.data, left_half, right_half)
		return Recursion_Min(root)


class Solution:

	def findMax(self, root):
		if root:
			return max(root.data, max(self.findMax(root.left), self.findMax(root.right)))
		else:
			return float('-inf')

	def findMin(self, root):
		if root:
			return min(root.data, min(self.findMin(root.left), self.findMin(root.right)))
		else:
			return float('inf')


class Solution:

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

	def findMax(self, root):
		l1 = []
		self.Isorder(root, l1)
		l1.sort()
		max1 = max(l1)
		return max1

	def findMin(self, root):
		l1 = []
		self.Isorder(root, l1)
		l1.sort()
		min1 = min(l1)
		return min1


class Solution:

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

	def findMax(self, root):
		v = []
		self.inorder(root, v)
		v.sort()
		return v[-1]

	def findMin(self, root):
		v = []
		self.inorder(root, v)
		v.sort()
		return v[0]


class Solution:

	def findMax(self, root):
		if root is None:
			return 0
		L = self.findMax(root.left)
		R = self.findMax(root.right)
		return max(root.data, max(L, R))

	def findMin(self, root):
		if root is None:
			return 10 ** 5
		L = self.findMin(root.left)
		R = self.findMin(root.right)
		return min(root.data, min(L, R))


class Solution:

	def findMax(self, root):
		if not root:
			return 0
		val = root.data
		left = self.findMax(root.left)
		right = self.findMax(root.right)
		return max(val, left, right)

	def findMin(self, root):
		if not root:
			return float('inf')
		val = root.data
		left = self.findMin(root.left)
		right = self.findMin(root.right)
		return min(val, left, right)


class Solution:

	def solve(self, root, q, s):
		if root:
			if root.data > q[len(q) - 1] and s == 1:
				q.append(root.data)
			elif root.data < q[len(q) - 1] and s == 0:
				q.append(root.data)
			if root.left:
				self.solve(root.left, q, s)
			if root.right:
				self.solve(root.right, q, s)
		return q

	def findMax(self, root):
		q = [0]
		q = self.solve(root, q, 1)
		return q[len(q) - 1]

	def findMin(self, root):
		q = [root.data]
		q = self.solve(root, q, 0)
		return q[len(q) - 1]


from collections import deque

class Solution:

	def bfs(self, root):
		queue = deque()
		queue.append(root)
		mx = 0
		mn = root.data
		while queue:
			node = queue.popleft()
			mx = max(node.data, mx)
			mn = min(mn, node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		return (mn, mx)

	def findMax(self, root):
		return self.bfs(root)[1]

	def findMin(self, root):
		return self.bfs(root)[0]


class Solution:

	def solve(self, root, s):
		if root:
			if root.data > q[len(q) - 1]:
				q.append(root.data)
			if root.data < q[len(q) - 1]:
				b.append(root.data)
			if root.left:
				self.solve(root.left, s)
			if root.right:
				self.solve(root.right, s)
		return q

	def findMax(self, root):
		global q, b
		q = [root.data]
		b = [root.data]
		self.solve(root, 1)
		return q[len(q) - 1]

	def findMin(self, root):
		global q, b
		return min(b)


class Solution:
	x = -1

	def findMax(self, root):
		res = [0, 10 ** 9]

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			if res[0] < root.data:
				res[0] = root.data
			if res[1] > root.data:
				res[1] = root.data
			inorder(root.right)
		inorder(root)
		global x
		if res[1] == 10 ** 9:
			x = -1
		else:
			x = res[1]
		return res[0] if res[0] != 0 else -1

	def findMin(self, root):
		return x


class Solution:

	def findMax(self, root):

		def inorder(root):
			if root is not None:
				inorder(root.left)
				a.append(root.data)
				inorder(root.right)
		a = []
		inorder(root)
		return max(a)

	def findMin(self, root):

		def inorder(root):
			if root is not None:
				inorder(root.left)
				a.append(root.data)
				inorder(root.right)
		a = []
		inorder(root)
		return min(a)


class Solution:

	def findMax(self, root):
		temp = root
		while temp.right:
			temp = temp.right
		return temp.data

	def findMin(self, root):
		temp = root
		while temp.left:
			temp = temp.left
		return temp.data


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		else:
			ls = self.findMax(root.left)
			rs = self.findMax(root.right)
		return max(root.data, ls, rs)

	def findMin(self, root):
		if root == None:
			return 99999999
		else:
			ls = self.findMin(root.left)
			rs = self.findMin(root.right)
		return min(root.data, min(ls, rs))


class Solution:

	def findMax(self, root):

		def fM(root):
			if root == None:
				return -1
			if root.left == None and root.right == None:
				return root.data
			return max(root.data, fM(root.left), fM(root.right))
		return fM(root)

	def findMin(self, root):

		def fMin(root):
			if root == None:
				return 999999999999
			if root.left == None and root.right == None:
				return root.data
			return min(root.data, fMin(root.left), fMin(root.right))
		return fMin(root)


class Solution:
	import sys
	mx = sys.maxsize

	def findMax(self, root):
		if root is None:
			return -self.mx
		if root.left is None and root.right is None:
			return root.data
		else:
			return max(self.findMax(root.left), self.findMax(root.right), root.data)

	def findMin(self, root):
		if root is None:
			return self.mx
		if root.left is None and root.right is None:
			return root.data
		else:
			return min(self.findMin(root.left), self.findMin(root.right), root.data)


class Solution:

	def findMax(self, root):
		s = [root.data]

		def inorder(root):
			if root != None:
				inorder(root.left)
				if s[0] < root.data:
					s[0] = root.data
				inorder(root.right)
		inorder(root)
		return s[0]

	def findMin(self, root):
		s = [root.data]

		def inorder(root):
			if root != None:
				inorder(root.left)
				if s[0] > root.data:
					s[0] = root.data
				inorder(root.right)
		inorder(root)
		return s[0]


import math

class Solution:

	def findMax(self, root):
		if root == None:
			return -math.inf
		else:
			leftsubtree = self.findMax(root.left)
			rightsubtree = self.findMax(root.right)
			return max(root.data, leftsubtree, rightsubtree)

	def findMin(self, root):
		if root == None:
			return math.inf
		else:
			leftsubtree = self.findMin(root.left)
			rightsubtree = self.findMin(root.right)
			return min(root.data, leftsubtree, rightsubtree)


class Solution:

	def findMax(self, root):
		stack = []
		stack.append(root)
		max_ele = -9999999
		while stack:
			ele = stack.pop()
			if ele.data > max_ele:
				max_ele = ele.data
			if ele.left:
				stack.append(ele.left)
			if ele.right:
				stack.append(ele.right)
		return max_ele

	def findMin(self, root):
		stack = []
		stack.append(root)
		min_ele = 9999999999
		while stack:
			ele = stack.pop()
			if ele.data < min_ele:
				min_ele = ele.data
			if ele.left:
				stack.append(ele.left)
			if ele.right:
				stack.append(ele.right)
		return min_ele


class Solution:

	def findMax(self, root):
		g = []

		def ans(root):
			if root != None:
				ans(root.left)
				g.append(root.data)
				ans(root.right)
			else:
				return
		ans(root)
		return max(g)

	def findMin(self, root):
		g = []

		def ans(root):
			if root != None:
				ans(root.left)
				g.append(root.data)
				ans(root.right)
			else:
				return
		ans(root)
		return min(g)


class Solution:

	def findMax(self, root):
		global arr
		arr = []

		def solve(root):
			if root:
				solve(root.left)
				arr.append(root.data)
				solve(root.right)
		solve(root)
		return max(arr)

	def findMin(self, root):

		def solve(root):
			if root:
				solve(root.left)
				arr.append(root.data)
				solve(root.right)
		solve(root)
		return min(arr)


class Solution:

	def findMax(self, root):

		def help(root):
			if root is None:
				return -1
			indL = help(root.left)
			indR = help(root.right)
			return max(indL, indR, root.data)
		ans = help(root)
		return ans

	def findMin(self, root):

		def help(root):
			if root is None:
				return 9999
			indL = help(root.left)
			indR = help(root.right)
			return min(indL, indR, root.data)
		ans = -1 if help(root) == 9999 else help(root)
		return ans


class Solution:

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

	def findMax(self, root):
		A = []
		self.x(root, A)
		return max(A)

	def findMin(self, root):
		A = []
		self.x(root, A)
		return min(A)


class Solution:

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

	def findMax(self, root):
		lis = []
		ans = self.solve(root, lis)
		return max(lis)

	def findMin(self, root):
		lis = []
		ans = self.solve(root, lis)
		return min(ans)


import math

class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		return max(self.findMax(root.left), self.findMax(root.right), root.data)

	def findMin(self, root):
		if root == None:
			return math.inf
		return min(self.findMin(root.left), self.findMin(root.right), root.data)


class Solution:

	def MinMax(self, root):
		if root == None:
			return (float('inf'), float('-inf'))
		else:
			(leftmin, leftmax) = self.MinMax(root.left)
			(rightmin, rightmax) = self.MinMax(root.right)
			return (min(leftmin, root.data, rightmin), max(leftmax, root.data, rightmax))

	def findMax(self, root):
		(minimum, maximum) = self.MinMax(root)
		return maximum

	def findMin(self, root):
		(minimum, maximum) = self.MinMax(root)
		return minimum


class Solution:

	def findMax(self, root):
		if root == None:
			return float('-inf')
		else:
			maxleft = self.findMax(root.left)
			maxright = self.findMax(root.right)
			return max(maxleft, root.data, maxright)

	def findMin(self, root):
		if root == None:
			return float('inf')
		else:
			minleft = self.findMin(root.left)
			minright = self.findMin(root.right)
			return min(minleft, root.data, minright)


import math

class Solution:

	def findMax(self, root):

		def traversal(root):
			nonlocal maximum
			if root == None:
				return None
			if root.data > maximum:
				maximum = root.data
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
		maximum = -math.inf
		traversal(root)
		return maximum

	def findMin(self, root):

		def traversal(root):
			nonlocal minimum
			if root == None:
				return None
			if root.data < minimum:
				minimum = root.data
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
		minimum = math.inf
		traversal(root)
		return minimum


class Solution:

	def findMax(self, root):
		b = []
		Solution.preorder(root, b)
		b.sort()
		return b[-1]

	def findMin(self, root):
		b = []
		Solution.preorder(root, b)
		b.sort()
		return b[0]

	def preorder(root, x):
		x.append(root.data)
		if root.left != None:
			Solution.preorder(root.left, x)
		if root.right != None:
			Solution.preorder(root.right, x)


class Solution:

	def findMax(self, root):
		maxe = root.data
		st = [root]
		while st:
			tamp = st.pop(0)
			if tamp.data > maxe:
				maxe = tamp.data
			if tamp.left:
				st.append(tamp.left)
			if tamp.right:
				st.append(tamp.right)
		return maxe

	def findMin(self, root):
		maxe = root.data
		st = [root]
		while st:
			tamp = st.pop(0)
			if tamp.data < maxe:
				maxe = tamp.data
			if tamp.left:
				st.append(tamp.left)
			if tamp.right:
				st.append(tamp.right)
		return maxe


class Solution:
	minn = 1000000
	maxx = -1

	def findMax(self, root):

		def helper(root):
			if root is None:
				return
			if root.data > self.maxx:
				self.maxx = root.data
			helper(root.left)
			helper(root.right)
		helper(root)
		return self.maxx

	def findMin(self, root):

		def helper(root):
			if root is None:
				return
			if root.data < self.minn:
				self.minn = root.data
			helper(root.left)
			helper(root.right)
		helper(root)
		return self.minn


import sys

class Solution:

	def findMax(self, root):
		if root is None:
			return -1
		leftlargest = self.findMax(root.left)
		rightlargest = self.findMax(root.right)
		largest = max(leftlargest, rightlargest, root.data)
		return largest

	def findMin(self, root):
		if root is None:
			return sys.maxsize
		leftsmallest = self.findMin(root.left)
		rightsmallest = self.findMin(root.right)
		smallest = min(leftsmallest, rightsmallest, root.data)
		return smallest


class Solution:

	def findMax(self, root):
		q = []
		max = -10000
		q.append(root)
		while len(q) > 0:
			t = q.pop(0)
			if t.left is not None:
				q.append(t.left)
			if t.right is not None:
				q.append(t.right)
			if t.data > max:
				max = t.data
		return max

	def findMin(self, root):
		q = []
		min = 10000
		q.append(root)
		while len(q) > 0:
			t = q.pop(0)
			if t.left is not None:
				q.append(t.left)
			if t.right is not None:
				q.append(t.right)
			if t.data < min:
				min = t.data
		return min


class Solution:

	def findMax(self, root):
		if root == None:
			return 0
		return max(root.data, self.findMax(root.left), self.findMax(root.right))

	def findMin(self, root):
		if root == None:
			return 10 ** 6
		return min(root.data, self.findMin(root.left), self.findMin(root.right))


class Solution:

	def findMax(self, root):
		max_ = float('-inf')

		def find_max(root):
			nonlocal max_
			if root:
				max_ = max(max_, root.data)
				find_max(root.left)
				find_max(root.right)
		find_max(root)
		return max_

	def findMin(self, root):
		min_ = float('inf')

		def find_min(root):
			nonlocal min_
			if root:
				min_ = min(min_, root.data)
				find_min(root.left)
				find_min(root.right)
		find_min(root)
		return min_