given two binary trees s and t check if t is a subtree of s a subtree of a tree t is a tree consisting of a node in t and all of its descendants in t example 1 given s 3 4 5 1 2 given t 4 1 2 return true because t is a subtree of s example 2 given s 3 4 5 1 2 0 given t 3 4 1 2 return false because even though t is part of s it does not contain all descendants of t follow up what if one tree is significantly lager than the other
import collections


def is_subtree(big, small):
    flag = False
    queue = collections.deque()
    queue.append(big)
    while queue:
        node = queue.popleft()
        if node.val == small.val:
            flag = comp(node, small)
            break
        else:
            queue.append(node.left)
            queue.append(node.right)
    return flag


def comp(p, q):
    if p is None and q is None:
        return True
    if p is not None and q is not None:
        return p.val == q.val and comp(p.left,q.left) and comp(p.right, q.right)
    return False