Subtree of Another Tree

Binary Tree
Easy

Approach

Diagrams

Analysis

Time

O(mn)

Space

O(n)
from collections import deque


class Solution:
    def isSubtree(self, tree, otherTree):
        if self.isSameTree(tree, otherTree):
            return True

        if tree is None:
            return False

        return self.isSubtree(tree.left, otherTree) or self.isSubtree(tree.right, otherTree)

    def isSameTree(self, root, otherRoot):
        queue = deque([(root, otherRoot)])

        while queue:
            node, otherNode = queue.popleft()

            if not (node or otherNode):
                continue

            if node is None or otherNode is None:
                return False

            if node.val != otherNode.val:
                return False

            queue.append((node.left, otherNode.left))
            queue.append((node.right, otherNode.right))

        return True

Learn

Videos