Check if subtree

/*
Logic:
isSubTree function will traverse the tree and where root->node of subtree matches with
current node of tree,then fun will be called which will check for subtree after current
node matches or not.

T.C O(mn) m,n is no. of nodes in both trees.
S.C O(n)

*/
def fun(root, sub):
    if not root and not sub:
        return True

    if not root or not sub:
        return False

    if root.data != sub.data:
        return False

    return fun(root.left, sub.left) and fun(root.right, sub.right)


class Solution:
    def isSubTree(self, t, s):
        if not s:
            return True
        if not t:
            return False

        a = False
        if t.data == s.data:
            a = fun(t, s)

        b = self.isSubTree(t.left, s)
        c = self.isSubTree(t.right, s)

        return a or b or c


//Method 2:
/*
 TC O(n)
 SC O(m+n)
 find preorder and inorder of both tree and if preorder of subtree is subarray of actual tree && inorder of subtree
 is subarray of actual tree,return true else false;
 use KMP for string matching.
IT can work with Preorder + inorder and Inorder+Postorder also.
*/