Given two binary trees with head reference as T and S having at most N nodes. The task is to check if S is present as subtree in T.
A subtree of a tree T1 is a tree T2 consisting of a node in T1 and all of its descendants in T1.
Example 1:
Input:
T:      1          S:   3
      /   \            /
     2     3          4
   /  \    /
  N    N  4
Output: 1 
Explanation: S is present in T
Example 2:
Input:
T:      26         S:   26
       /   \           /  \
     10     N        10    N
   /    \           /  \
   20    30        20  30
  /  \            /  \
 40   60         40  60
Output: 1 
Explanation: 
S and T are both same. Hence, 
it can be said that S is a subtree 
of T.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isSubtree() that takes root node of S and T as parameters and returns 1 if S is a subtree of T else 0.
Note: The nodes can have the duplicate values.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Value of nodes <= 10^{4}

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3









'''

class Node:

    def _init_(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

# your task is to complete this function

# function should print the left view of the binary tree

# Note: You aren't required to print a new line after every test case





class Solution:

    def isSubTree(self, T, S):

        # Code here

Solutions:
class Solution:

	def check(self, T, S):
		if S == None and T == None:
			return 1
		if T != None and S == None or (T == None and S != None):
			return 0
		l = self.check(T.left, S.left)
		r = self.check(T.right, S.right)
		if T.data == S.data and l == 1 and (r == 1):
			return 1
		else:
			return 0

	def isSubTree(self, T, S):
		q = [T]
		while len(q) > 0:
			temp = q[0]
			q.pop(0)
			if temp.data == S.data:
				if self.check(temp, S) == 1:
					return True
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
		return False


class Node:

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

class Solution:

	def isIdentical(self, root1, root2):
		if root1 is None and root2 is None:
			return True
		if root1 is None or root2 is None:
			return False
		return root1.data == root2.data and self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		if self.isIdentical(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def isSubTree(self, T, S):
		root1 = T
		root2 = S

		def fun(root1, root2):
			if root1 is None and root2 is None:
				return True
			if root1 is None and root2 is not None:
				return False
			if root1 is not None and root2 is None:
				return False
			if root1.data == root2.data:
				if fun(root1.left, root2.left) and fun(root1.right, root2.right):
					return True
			return fun(root1.left, root2) or fun(root1.right, root2)
		return fun(root1, root2)


class Solution:

	def isSubTree(self, T, S):
		if not T:
			return False
		if not S:
			return True
		if self.isSameTree(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)

	def isSameTree(self, t, s):
		if not t and (not s):
			return True
		if not t or not s or t.data != s.data:
			return False
		return self.isSameTree(t.left, s.left) and self.isSameTree(t.right, s.right)


class Solution:

	def isSubTree(self, T, S):
		alls = []

		def finds(root):
			if not root:
				return
			if root.data == S.data:
				alls.append(root)
			finds(root.left)
			finds(root.right)

		def isSame(r1, r2):
			if not r1 and (not r2):
				return True
			if r1 and r2:
				return r1.data == r2.data and isSame(r1.left, r2.left) and isSame(r1.right, r2.right)
			return False
		finds(T)
		ans = False
		for ns in alls:
			nans = isSame(ns, S)
			ans = nans | ans
		return ans


class Solution:

	def isIdentical(self, T, S):
		if T is None and S is None:
			return True
		if T is None or S is None:
			return False
		if T.data == S.data:
			return self.isIdentical(T.left, S.left) and self.isIdentical(T.right, S.right)
		return False

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		return self.isIdentical(T, S) or self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def isSubTree(self, T, S):

		def func(root, p):

			def inorder(root):
				if root == None:
					return '$'
				s = inorder(root.left)
				s += str(root.data)
				s += inorder(root.right)
				return s

			def postorder(root):
				if root == None:
					return '$'
				s = postorder(root.left)
				s += postorder(root.right)
				s += str(root.data)
				return s
			(inorderT, postorderT) = (inorder(root), postorder(root))
			(inorderS, postorderS) = (inorder(p), postorder(p))
			if inorderS in inorderT and postorderS in postorderT:
				return True
			return False
		return func(T, S)


class Solution:

	def isSubTree(self, T, S):

		def func(root, p):
			if root == None and p == None:
				return True
			if root == None or p == None:
				return False
			ans = False
			if root.data == p.data:
				ans = func(root.left, p.left) and func(root.right, p.right)
			ans = ans or func(root.left, p) or func(root.right, p)
			return ans
		return func(T, S)


class Solution:

	def storeInorder(self, root):
		if root == None:
			return '$'
		res = self.storeInorder(root.left)
		res += str(root.data)
		res += self.storeInorder(root.right)
		return res

	def storePreOrder(self, root):
		if root == None:
			return '$'
		res = str(root.data)
		res += self.storePreOrder(root.left)
		res += self.storePreOrder(root.right)
		return res

	def isSubTree(self, T, S):
		if S == None:
			return True
		if T == None:
			return False
		inS = self.storeInorder(S)
		inT = self.storeInorder(T)
		res = True
		if inS in inT:
			res = True
		else:
			res = False
		if res == False:
			return res
		preS = self.storePreOrder(S)
		preT = self.storePreOrder(T)
		if preS in preT:
			return True
		return False


class Solution:

	def check(self, T, S):
		if T == None and S == None:
			return True
		if T == None or S == None:
			return False
		if T.data == S.data:
			return self.check(T.left, S.left) and self.check(T.right, S.right)
		return 0

	def isSubTree(self, T, S):
		if S == None:
			return True
		if T == None:
			return False
		if T.data == S.data:
			if self.check(T, S):
				return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def inorder(self, T, li):
		if T:
			self.inorder(T.left, li)
			self.inorder(T.right, li)
			li.append(T.data)
		else:
			li.append(None)

	def isSubTree(self, T, S):
		li = []
		self.inorder(T, li)
		li1 = []
		self.inorder(S, li1)
		for i in range(len(li) - len(li1) + 1):
			if li[i:i + len(li1)] == li1:
				return True
		return False


class Solution:

	def isSubTree(self, T, S):
		li = []

		def inorder(node):
			nonlocal li
			if node:
				li.append(node.data)
				inorder(node.left)
				inorder(node.right)
			else:
				li.append(None)
			return li
		a = inorder(T)
		li = []
		b = inorder(S)
		for i in range(len(a) - len(b) + 1):
			if a[i:i + len(b)] == b:
				return True
		return False


class Solution:

	def isSubTree(self, root, subRoot):

		def checkSame(head1, head2):
			if head1 and (not head2):
				return False
			if not head1 and head2:
				return False
			if not head1 and (not head2):
				return True
			if head1.data != head2.data:
				return False
			return checkSame(head1.left, head2.left) and checkSame(head1.right, head2.right)

		def f(root):
			if not root:
				return False
			if root:
				if root.data == subRoot.data:
					us = checkSame(root, subRoot)
				else:
					us = False
				left = f(root.left)
				right = f(root.right)
				return us or left or right
		return f(root)


class Solution:

	def sub(self, t, s):
		if t == None and s == None:
			return True
		if t == None or s == None:
			return False
		return t.data == s.data and self.sub(t.left, s.left) and self.sub(t.right, s.right)

	def isSubTree(self, t, s):
		if t == None:
			return False
		if s == None:
			return False
		if self.sub(t, s):
			return True
		return self.isSubTree(t.left, s) or self.isSubTree(t.right, s)


class Solution:

	def isSubTree(self, T, S):
		if T is None:
			return False
		if S is None:
			return True
		if self.is_identical(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)

	def is_identical(self, a, b):
		if a is None and b is None:
			return True
		if a is None or b is None or a.data != b.data:
			return False
		return self.is_identical(a.left, b.left) and self.is_identical(a.right, b.right)


class Solution:

	def isSubTree(self, T, S):

		def fun(r, l):
			if r == None:
				l.append('N')
				return
			l.append('^')
			l.append(r.data)
			fun(r.left, l)
			fun(r.right, l)
		(l1, l2) = ([], [])
		fun(T, l1)
		fun(S, l2)
		(s1, s2) = ('', '')
		for i in l1:
			s1 += str(i)
		for i in l2:
			s2 += str(i)
		if s2 in s1:
			return True


class Solution:

	def identical(self, r1, r2):
		if r1 == None and r2 == None:
			return True
		if r1 == None or r2 == None:
			return False
		return r1.data == r2.data and self.identical(r1.left, r2.left) and self.identical(r1.right, r2.right)

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		if self.identical(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def isSubTree(self, T, S):

		def match(a, b):
			if not a and (not b):
				return True
			if not a and b or (not b and a):
				return False
			if a.data != b.data:
				return False
			return match(a.left, b.left) and match(a.right, b.right)

		def traverse(root):
			if not root:
				return False
			out = match(root, S)
			if out:
				return out
			return traverse(root.left) or traverse(root.right)
		return traverse(T)


class Solution:

	def findAll(self, root, val):
		ans = []
		if root == None:
			return
		if root.left:
			ans.extend(self.findAll(root.left, val))
		if root.right:
			ans.extend(self.findAll(root.right, val))
		if root.data == val:
			ans.append(root)
		return ans

	def same(self, root1, root2):
		if root1 == None and root2 == None:
			return True
		if root1 == None and root2 != None or (root1 != None and root2 == None):
			return False
		left = self.same(root1.left, root2.left)
		right = self.same(root1.right, root2.right)
		val = True
		if root1.data != root2.data:
			val = False
		if left and right and val:
			return True
		else:
			return False

	def isSubTree(self, T, S):
		li = self.findAll(T, S.data)
		s = S
		while li:
			f = li.pop()
			if self.same(f, s):
				return True
		return False


class Solution:

	def isSubTree(self, T, S):
		if T == None:
			return False
		if S == None:
			return True
		if self.areId(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)

	def areId(self, root1, root2):
		if root1 == None and root2 == None:
			return True
		if root1 == None or root2 == None:
			return False
		return root1.data == root2.data and self.areId(root1.left, root2.left) and self.areId(root1.right, root2.right)


class Solution:

	def isSubTree(self, T, S):

		def check(r1, r2):
			if r1 == r2 == None:
				return True
			elif r1 and r2 and (r1.data == r2.data):
				if check(r1.left, r2.left) == False:
					return False
				if check(r1.right, r2.right) == False:
					return False
				return True
			else:
				return False

		def validate(T, S):
			if T == None:
				return False
			elif T and S and (T.data == S.data) and check(T, S):
				return True
			else:
				if validate(T.left, S):
					return True
				if validate(T.right, S):
					return True
				return False
		return validate(T, S)


sol = False

class Solution:

	def isSubTree(self, T, S):
		if T == None:
			return False
		elif Solution._isSubtree(self, T, S):
			return True
		return Solution.isSubTree(self, T.left, S) or Solution.isSubTree(self, T.right, S)

	def _isSubtree(self, T, S):
		if T == None and S == None:
			return True
		elif T == None or S == None:
			return False
		return T.data == S.data and Solution._isSubtree(self, T.left, S.left) and Solution._isSubtree(self, T.right, S.right)


class Solution:

	def isSubTree(self, T, S):

		def f(t1, t2):
			if t1 == None and t2 == None:
				return True
			if t1 == None or t2 == None:
				return False
			return t1.data == t2.data and f(t1.left, t2.left) and f(t1.right, t2.right)

		def k(t1, t2):
			if t1 == None and t2 == None:
				return True
			if t1 == None:
				return False
			return f(t1, t2) or k(t1.left, t2) or k(t1.right, t2)
		return k(T, S)


class Solution:

	def isSubTree(self, T, S):
		self.findLs = []
		self.trav(T, S)
		if self.findLs:
			for r in self.findLs:
				self.chk = True
				self.chkSubtree(r, S)
				if self.chk is True:
					return True
			return False
		else:
			return False

	def trav(self, root, S):
		if root is None:
			return
		if root.data == S.data:
			self.findLs.append(root)
		self.trav(root.left, S)
		self.trav(root.right, S)

	def chkSubtree(self, r1, r2):
		if self.chk == False:
			return
		if r1 is None and r2 is None:
			return
		if r1 is None:
			self.chk = False
			return
		if r2 is None:
			self.chk = False
			return
		if r1.data != r2.data:
			self.chk = False
			return
		self.chkSubtree(r1.left, r2.left)
		self.chkSubtree(r1.right, r2.right)


class Solution:

	def isSubTree(self, T, S):

		def helpii(s):
			if not s:
				return 'N'
			return helpii(s.left) + ',' + str(s.data) + helpii(s.right)

		def helpip(s):
			if not s:
				return 'N'
			return ',' + str(s.data) + helpip(s.left) + helpip(s.right)
		x = helpii(S)
		y = helpii(T)
		a = helpip(S)
		b = helpip(T)
		if x in y:
			return a in b
		else:
			return False


class Solution:

	def isSubTree(self, T, S):
		if T == None:
			return False
		left = self.isSubTree(T.left, S)
		right = self.isSubTree(T.right, S)
		if left or right:
			return True
		return self.sub(T, S)

	def sub(self, T, S):
		if T == None and S == None:
			return True
		if T == None or S == None:
			return False
		root = T.data == S.data
		left = self.sub(T.left, S.left)
		right = self.sub(T.right, S.right)
		return root and left and right


from collections import deque

class Solution:

	def isSubTreeUtil(self, node1, node2):
		if not node1 and (not node2):
			return True
		if not node1 or not node2:
			return False
		if node1.data != node2.data:
			return False
		return self.isSubTreeUtil(node1.right, node2.right) and self.isSubTreeUtil(node1.left, node2.left)

	def isSubTree(self, T, S):
		if not T:
			return False
		return self.isSubTreeUtil(T, S) or self.isSubTree(T.right, S) or self.isSubTree(T.left, S)


class Solution:

	def isSubTree(self, T, S):
		l = []

		def find(root, root1):
			if root == None:
				return
			if root.data == root1.data:
				l.append(root)
			find(root.left, root1)
			find(root.right, root1)
		find(T, S)

		def check(root1, root2):
			if root1 == None and root2 != None:
				return False
			if root1 != None and root2 == None:
				return False
			if root1 == None and root2 == None:
				return True
			if root1.data != root2.data:
				return False
			return root1.data == root2.data and check(root1.left, root2.left) and check(root1.right, root2.right)
		A = False
		for i in l:
			A = A or check(i, S)
		return A


class Solution:

	def checkIfSubTree(self, tree1, tree2):
		q1 = []
		q2 = []
		q1.append(tree1)
		q2.append(tree2)
		while len(q1):
			if len(q1) != len(q2):
				return False
			queue1 = []
			queue2 = []
			for i in range(0, len(q1)):
				(node1, node2) = (q1[i], q2[i])
				if node1 is None and node2 is not None or (node1 is not None and node2 is None):
					return False
				if node1 is None and node2 is None:
					continue
				if node1.data != node2.data:
					return False
				queue1.append(node1.left)
				queue2.append(node2.left)
				queue1.append(node1.right)
				queue2.append(node2.right)
			q1 = queue1
			q2 = queue2
		return True

	def findMatchingNode(self, node, root):
		if node is None:
			return False
		if node.data == root.data:
			if self.checkIfSubTree(node, root):
				return True
		return self.findMatchingNode(node.left, root) or self.findMatchingNode(node.right, root)

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		return self.findMatchingNode(T, S)


class Solution:

	def isSubTree(self, T, S):

		def dfs(T, S):
			if not T and (not S):
				return True
			elif not T or not S:
				return False
			elif T.data != S.data:
				return False
			return dfs(T.left, S.left) and dfs(T.right, S.right)
		if not T and (not S):
			return True
		if not S:
			return True
		if not T:
			return False
		if T.data == S.data and dfs(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def isSubTree(self, T, S):

		def helper(roott, roots):
			if roott == None and roots == None:
				return True
			if roott == None or roots == None:
				return False
			if roott.data == roots.data:
				left = helper(roott.left, roots.left)
				right = helper(roott.right, roots.right)
				if left and right:
					return True
			left = helper(roott.left, roots)
			right = helper(roott.right, roots)
			return left or right
		return helper(T, S)


class Solution:

	def isSubTree(self, T, S):
		if not S:
			return True
		if not T:
			return False
		if S.data == T.data:
			if self.checkIdentical(T, S):
				return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)

	def checkIdentical(self, n1, n2):
		if not n1 and (not n2):
			return True
		if not n1 or not n2:
			return False
		return n1.data == n2.data and self.checkIdentical(n1.left, n2.left) and self.checkIdentical(n1.right, n2.right)


class Solution:

	def isSubTree(self, t, s):

		def same_tree(root1, root2):
			if root1 and root2:
				return root1.data == root2.data and same_tree(root1.left, root2.left) and same_tree(root1.right, root2.right)
			return root1 == root2

		def subtree(root1, root2):
			if root1 == None:
				return False
			if same_tree(root1, root2):
				return True
			return subtree(root1.left, root2) or subtree(root1.right, root2)
		if subtree(t, s):
			return True
		return False


class Solution:

	def isSubTree(self, T, S):
		inT = self.inOrder(T)
		inS = self.inOrder(S)
		preT = self.preOrder(T)
		preS = self.preOrder(S)
		return inS in inT and preS in preT

	def inOrder(self, root):
		if not root:
			return '$'
		inL = self.inOrder(root.left)
		inR = self.inOrder(root.right)
		return inL + str(root.data) + inR

	def preOrder(self, root):
		if not root:
			return 'N'
		preL = self.preOrder(root.left)
		preR = self.preOrder(root.right)
		return str(root.data) + preL + preR


class Solution:

	def isSubTree(self, T, S):
		self.tRoot = S
		self.found = False
		return self.traverse(T, S)

	def traverse(self, sNode, tNode):
		(left, right) = (None, None)
		if sNode.data == tNode.data:
			while True:
				if sNode.left or tNode.left:
					if sNode.left and tNode.left:
						left = self.traverse(sNode.left, tNode.left)
						if not left:
							break
					else:
						break
				if self.found:
					return True
				if sNode.right or tNode.right:
					if sNode.right and tNode.right:
						right = self.traverse(sNode.right, tNode.right)
						if not right:
							break
					else:
						break
				if tNode == self.tRoot:
					self.found = True
				return True
				break
		if sNode.left:
			self.traverse(sNode.left, self.tRoot)
			if self.found:
				return True
		if sNode.right:
			self.traverse(sNode.right, self.tRoot)
			if self.found:
				return True
		return False


class Solution:

	def sub(self, root, x):
		if root == None and x == None:
			return True
		if root == None or x == None:
			return False
		return root.data == x.data and self.sub(root.left, x.left) and self.sub(root.right, x.right)

	def tra(self, root, x, a, ans):
		if root == None:
			return (a, ans)
		if a == True:
			return (a, ans)
		if root.data == x.data:
			a = self.sub(root, x)
			if a == True:
				ans = True
			if a == True:
				return (a, ans)
		(a, ans) = self.tra(root.left, x, a, ans)
		(a, ans) = self.tra(root.right, x, a, ans)
		return (a, ans)

	def isSubTree(self, T, S):
		if T != None and S == None or (T == None and S != None):
			return 0
		(a, b) = self.tra(T, S, False, False)
		return b


class Solution:

	def isSubTree(self, T, S):

		def helper(t, s):
			if t == None and s == None:
				return True
			elif t == None and s != None:
				return False
			elif s == None and t != None:
				return False
			elif s.data != t.data:
				return False
			return helper(t.left, s.left) and helper(t.right, s.right)

		def find(s, t):
			if s == None:
				return False
			ls = helper(s, t)
			if ls:
				return True
			else:
				return find(s.left, t) or find(s.right, t)
		return find(T, S)


class Solution:

	def isSubTree(self, T, S):
		self.ans = False

		def sametree(root1, root2):
			if root1 is None and root2 is None:
				return True
			if root1 is None or root2 is None:
				return False
			return root1.data == root2.data and sametree(root1.left, root2.left) and sametree(root1.right, root2.right)

		def func(t, s):
			if t is None:
				return
			if t.data == s.data:
				kk = sametree(t, s)
				if kk:
					self.ans = True
					return
			func(t.left, s)
			func(t.right, s)
		func(T, S)
		return self.ans


class Solution:

	def isSubTree(self, T, S):

		def isidentical(a, b):
			if a == None and b == None:
				return True
			if a != None and b != None:
				issamedata = a.data == b.data
				issameleft = isidentical(a.left, b.left)
				issameright = isidentical(a.right, b.right)
				return issamedata and issameleft and issameright
			return False

		def issubtree(a, b):
			if b == None:
				return True
			if a == None and b != None:
				return False
			if isidentical(a, b):
				return True
			leftcheck = issubtree(a.left, b)
			rightcheck = issubtree(a.right, b)
			return leftcheck or rightcheck
		return issubtree(T, S)


class Solution:

	def isSubTree(self, T, S):
		b = []
		Solution.target(T, S, b)
		if len(b) != 0:
			for i in b:
				x = []
				Solution.bst(i, x)
				y = []
				Solution.bst(S, y)
				if x == y:
					return True
			return False
		return False

	def target(root, S, b):
		if root.data == S.data:
			b.append(root)
		if root.left != None:
			Solution.target(root.left, S, b)
		if root.right != None:
			Solution.target(root.right, S, b)
		return

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


class Solution:

	def sameTree(self, root1, root2):
		if not root1 and (not root2):
			return True
		elif not root1 or not root2:
			return False
		elif root1.data == root2.data and self.sameTree(root1.left, root2.left) and self.sameTree(root1.right, root2.right):
			return True
		else:
			return False

	def isSubTree(self, T, S):
		if not T:
			return False
		if T.data == S.data:
			if self.sameTree(T, S):
				return True
		l = self.isSubTree(T.left, S)
		r = self.isSubTree(T.right, S)
		return l or r


class Solution:

	def isSubTree(self, t, s):
		if t == None:
			if s == None:
				return True
			return False
		if self.isIdentical(s, t):
			return True
		return self.isSubTree(t.left, s) or self.isSubTree(t.right, s)

	def isIdentical(self, root1, root2):
		if root1 and root2:
			if root1.data != root2.data:
				return False
			return self.isIdentical(root1.left, root2.left) and self.isIdentical(root1.right, root2.right)
		elif root1 == None and root2 == None:
			return True
		else:
			return False


def match(T1, T2):
	if T1 and T2:
		return T1.data == T2.data and match(T1.left, T2.left) and match(T1.right, T2.right)
	elif T1 or T2:
		return False
	else:
		return True

class Solution:

	def isSubTree(self, T, S):
		if T == None:
			return False
		return T.data == S.data and match(T, S) or self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


def check(t, s):
	if not s and (not t):
		return True
	if s and t and (t.data == s.data):
		return check(t.left, s.left) and check(t.right, s.right)
	return False

class Solution:

	def isSubTree(self, t, s):
		if not t:
			return False
		if not s:
			return True
		if check(t, s):
			return True
		return self.isSubTree(t.left, s) or self.isSubTree(t.right, s)


def isame(root, sub):
	if root == None and sub == None:
		return True
	if root != None and sub != None and (root.data == sub.data):
		l = isame(root.left, sub.left)
		r = isame(root.right, sub.right)
		if l and r:
			return True
		return False
	return False

class Solution:

	def isSubTree(self, root, subRoot):
		if subRoot == None:
			return True
		if root == None:
			return False
		if isame(root, subRoot):
			return True
		else:
			l = self.isSubTree(root.left, subRoot)
			r = self.isSubTree(root.right, subRoot)
			return l or r


class Solution:

	def __init__(self):
		self.res = False
		self.q = []

	def on(self, a):
		if a == None:
			return [None]
		g = self.on(a.left)
		h = self.on(a.right)
		o = g + [a.data] + h
		return o

	def off(self, a, b):
		if a == None:
			return [None]
		p = self.off(a.left, b)
		q = self.off(a.right, b)
		r = p + [a.data] + q
		if r == self.q:
			self.res = True
		return r

	def isSubTree(self, T, S):
		self.q = self.on(S)
		self.off(T, S)
		return self.res


class Solution:

	def isSubTree(self, root1, root2):
		serialset = set()

		def serialize(root, addToSet=False):
			if not root:
				return '#'
			serial_id = str(root.data) + ',' + serialize(root.left, addToSet) + ',' + serialize(root.right, addToSet)
			if addToSet:
				serialset.add(serial_id)
			return serial_id
		serialize(root1, True)
		return serialize(root2) in serialset


def check(root, node):
	if not root and (not node):
		return True
	if not root and node:
		return False
	if not node and root:
		return False
	if root.data == node.data:
		return check(root.left, node.left) and check(root.right, node.right)
	return False

class Solution:

	def isSubTree(self, T, S):
		if not S:
			return True
		if not T:
			return False
		if T.data == S.data:
			if check(T, S):
				return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Node:

	def _init_(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def isSubTree(self, T, S):
		if T == None and S == None:
			return True
		if T == None or S == None:
			return False
		if T.data == S.data:
			return self.isSubTree(T.left, S.left) and self.isSubTree(T.right, S.right) or (self.isSubTree(T.left, S) or self.isSubTree(T.right, S))
		else:
			return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def isSubTree(self, T, S):
		return self.inOrder(S) in self.inOrder(T)

	def inOrder(self, root):
		if not root:
			return '/'
		return '^' + str(root.data) + '#' + self.inOrder(root.left) + self.inOrder(root.right)


class Solution:

	def isSubTree(self, T, S):
		indexes = []
		stack1 = []
		stack2 = []
		self.helper(T, stack1, indexes, S)
		self.helper(S, stack2, [], S)
		for i in indexes:
			if stack1[i:i + len(stack2)] == stack2:
				return True
		return False

	def helper(self, root, stack, indexes, aux):
		if root:
			if root.data == aux.data:
				indexes.append(len(stack))
			stack.append(root.data)
			self.helper(root.left, stack, indexes, aux)
			self.helper(root.right, stack, indexes, aux)
		else:
			stack.append('N')


def are_identical(subtree_a, subtree_b):
	if subtree_a is None and subtree_b is None:
		return True
	if subtree_a is None or subtree_b is None or subtree_a.data != subtree_b.data:
		return False
	return are_identical(subtree_a.left, subtree_b.left) and are_identical(subtree_a.right, subtree_b.right)

class Solution:

	def isSubTree(self, T, S):
		if T is None:
			return False
		if S is None:
			return True
		if are_identical(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)


class Solution:

	def height(self, root):
		if root == None:
			return 0
		left = self.height(root.left)
		right = self.height(root.right)
		return left + 1 if left > right else right + 1

	def nodesAtSameHeight(self, root, h, lst):
		if root == None:
			return 0
		left = self.nodesAtSameHeight(root.left, h, lst)
		right = self.nodesAtSameHeight(root.right, h, lst)
		ans = left + 1 if left > right else right + 1
		if ans == h:
			lst.append(root)
		return ans

	def find(self, root1, root2):
		if not root1 and (not root2):
			return True
		if root1 and (not root2) or (root2 and (not root1)):
			return False
		if root1.data != root2.data:
			return False
		return self.find(root1.left, root2.left) and self.find(root1.right, root2.right)

	def isSubTree(self, T, S):
		if not T and (not S):
			return True
		if T and (not S) or (S and (not T)):
			return False
		h = self.height(S)
		lst = []
		self.nodesAtSameHeight(T, h, lst)
		for node in lst:
			ans = self.find(node, S)
			if ans == True:
				return True
		return False


class Solution:

	def isSubTree(self, T, S):
		global j, k
		k = -1
		j = 0

		def sol1(A, B):
			if not A and (not B):
				return True
			elif not A:
				return False
			elif not B:
				return False
			if A and B:
				if A.data != B.data:
					return False
				q = sol1(A.left, B.left)
				p = sol1(A.right, B.right)
				if p and q:
					return True
				else:
					return False
			return False

		def Tree(T, S):
			global j, k
			if T:
				o = sol1(T, S)
				if o == True:
					j = 1
				Tree(T.left, S)
				Tree(T.right, S)
		Tree(T, S)
		if j == 1:
			return True
		return False


class Solution:

	def isSub(self, curr1, curr2):
		if not curr1:
			return not curr2
		if curr1 and (not curr2):
			return False
		if not curr1.data == curr2.data:
			return False
		ans1 = self.isSub(curr1.left, curr2.left)
		ans2 = self.isSub(curr1.right, curr2.right)
		return ans1 and ans2

	def isSubTree(self, T, S):
		if not T:
			return not S
		queue = [T]
		child = S
		while queue:
			curr = queue.pop(0)
			if curr.data == child.data:
				if self.isSub(curr, child):
					return True
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
		return False


class Solution:

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		if self.same(T, S):
			return True
		return self.isSubTree(T.left, S) or self.isSubTree(T.right, S)

	def same(self, x, y):
		if x is None and y is None:
			return True
		if x and y:
			return x.data == y.data and self.same(x.left, y.left) and self.same(x.right, y.right)
		return False


class Solution:

	def isSubTree(self, T, S):
		if S is None:
			return True
		if T is None:
			return False
		(mani, sani) = ([], [])
		self.serial(T, mani)
		self.serial(S, sani)
		mis = ''.join(mani)
		sis = ''.join(sani)
		return sis in mis

	def serial(self, T, res):
		if T is None:
			res.append('#')
			return
		res.append('^')
		res.append(str(T.data))
		self.serial(T.left, res)
		self.serial(T.right, res)