60. Subtree of Another Tree
Problem Statement
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
Solution
# 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
class Solution:
def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
if not root:
return False
if not subRoot:
return True # An empty tree is always a subtree
# Check if the current root and subRoot are the same tree
if self.isSameTree(root, subRoot):
return True
# Otherwise, check if subRoot is a subtree of root.left or root.right
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# Base Case 1: Both are None, they are the same
if not p and not q:
return True
# Base Case 2: One is None and the other is not, they are different
if not p or not q:
return False
# Base Case 3: Values are different, they are different
if p.val != q.val:
return False
# Recursive Step: Check left subtrees and right subtrees
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Explanation
This problem combines two concepts: checking if two trees are identical and traversing a tree to find a match.
Core Idea: We need to check if subRoot
is identical to root
, or if subRoot
is identical to any of root
's subtrees (left or right).
Recursive Approach:
-
isSubtree(root, subRoot)
Function:- Base Case 1 (
root
isNone
): If theroot
of the main tree isNone
, thensubRoot
cannot be a subtree (unlesssubRoot
is alsoNone
, which is handled by the next base case). So, returnFalse
. - Base Case 2 (
subRoot
isNone
): IfsubRoot
isNone
, an empty tree is considered a subtree of any tree. ReturnTrue
. - Check for Identity: First, we check if the current
root
andsubRoot
are exactly the same tree using a helper functionisSameTree
. If they are, we've found our subtree, so returnTrue
. - Recurse on Subtrees: If they are not the same, we recursively check if
subRoot
is a subtree ofroot.left
ORroot.right
. Theor
condition is important becausesubRoot
could be found in either branch.
- Base Case 1 (
-
isSameTree(p, q)
Helper Function: This is a standard function to check if two binary trees are identical (same structure and same values). It has the following logic:- If both
p
andq
areNone
, returnTrue
. - If one is
None
and the other is not, returnFalse
. - If their values are different, return
False
. - Otherwise, recursively check if their left children are the same AND their right children are the same.
- If both
Time and Space Complexity:
- Time Complexity: O(M * N), where M is the number of nodes in
root
and N is the number of nodes insubRoot
. In the worst case, for each node inroot
, we might perform aisSameTree
comparison which takes O(N) time. - Space Complexity: O(H_root + H_subRoot) in the worst case, where H is the height of the respective trees, due to the recursion stack.