# 572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example1:

Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4 
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.

Example2:

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
 Return false.

# Solution

Approach 1: recursive -- look for t within s by comparing nodes. Time: up to O(m*n) where s has m nodes & t has n nodes; space: O(m) -- the depth of recursion.

Approach 2: iterative -- same idea. Space now is O(m) + O(n).

# Code (Python)

Approach 1:

class Solution:
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if not s and not t:
            return True
        if (s and not t) or (t and not s):
            return False
        if s.val == t.val and self._is_same_tree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    def _is_same_tree(self, t1, t2):
        if not t1 and not t2:
            return True
        if (t1 and not t2) or (t2 and not t1) or t1.val != t2.val:
            return False
        return (t1.val == t2.val and 
                self._is_same_tree(t1.left, t2.left) and 
                self._is_same_tree(t1.right, t2.right))

Approach 2:

    def isSubtree(self, s, t):
        # iterative: also look for t within s by comparing nodes
        if not s:
            return not t
        node = s
        stack = []
        while node:
            stack.append(node)
            node = node.left
        while stack:
            node = stack.pop()
            if node.val == t.val and self._is_same_tree_iterative(node, t):
                return True
            node = node.right
            while node:
                stack.append(node)
                node = node.left
        return False
    
    def _is_same_tree_iterative(self, t1, t2):
        stack1, stack2 = [t1], [t2]
        while stack1 and stack2:
            n1, n2 = stack1.pop(), stack2.pop()
            if n1.val != n2.val:
                return False
            if n1.right and n2.right:
                stack1.append(n1.right)
                stack2.append(n2.right)
            elif (n1.right and not n2.right) or (n2.right and not n1.right):
                return False
            if n1.left and n2.left:
                stack1.append(n1.left)
                stack2.append(n2.left)
            elif (n1.left and not n2.left) or (n2.left and not n1.left):
                return False
        return not stack1 and not stack2

# Code (C++)

Approach 1:

Approach 2: