Problem Description
Given the roots of two binary trees root and subRoot, return True if there is a subtree of root with the same structure and node values of subRoot and False otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
Example 1:
- Input:
root = [3,4,5,1,2], subRoot = [4,1,2] - Output:
True
Example 2:
- Input:
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] - Output:
False
My Idea
My idea here was to utilize the isSameTree(p,q) function from 100. Same Tree and at each node of root check if the tree starting at the current node is the same as subRoot. This was the most intuitive solution to me and yielded a time complexity of O(n*m). As is was fast enough, i didn’t bother implementing a faster algorithm, however, it is possible to traverse each of the trees once and serialize it and then check if the serialization of subRoot is a substring of the serialization of root, which will have a time complexity of O(n+m).
My solution
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Time Complexity: O(n*m)
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
if (not p and q) or (not q and p):
return False
if p.val == q.val:
return True and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
else:
return False
if not root and not subRoot:
return True
if not root and subRoot:
return False
if root and not subRoot:
return True
if isSameTree(root,subRoot):
return True
return isSubtree(root.left,subRoot) or isSubtree(root.right,subRoot)