## # 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:

``````
``````