572. Subtree of Another Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 44.6%
Problem Breakdown
The problem asks us to determine whether a given binary tree t is a subtree of another binary tree s. A subtree of s is defined as a node in s and all its descendants. The structure and node values must match exactly.
Inputs:
- Two non-empty binary trees,
s(the main tree) andt(the potential subtree).
Outputs:
- A boolean value indicating whether
tis a subtree ofs.
Implicit Constraints or Tricky Edge Cases:
- The trees can be large.
- The values in the nodes could be negative or zero.
- The trees might have duplicate values.
Intuition
A brute-force approach would involve checking every node in s to see if it matches the structure and values of t. This would result in a time complexity of O(n * m), where n is the number of nodes in s and m is the number of nodes in t.
The key insight is that we can use a recursive approach to check if any subtree of s is identical to t. We can leverage the properties of binary trees and perform a tree traversal to compare each node.
Approach
- Recursive Function: Define a helper function
is_identicalthat checks if two trees are identical (i.e., have the same structure and values). - Base Case for
is_identical:- If both nodes are null, return true.
- If one node is null and the other is not, return false.
- If the values of the current nodes are different, return false.
- Recursive Case for
is_identical:- Recursively check if the left subtrees are identical.
- Recursively check if the right subtrees are identical.
- Main Function: Define a function
is_subtreethat checks iftis a subtree ofs. - Base Case for
is_subtree:- If
sis null, return false (since an empty tree cannot contain another non-empty tree).
- If
- Recursive Case for
is_subtree:- Check if the current nodes of
sandtare identical usingis_identical. - Recursively check if
tis a subtree of the left or right subtree ofs.
- Check if the current nodes of
Complexity Analysis
- Time Complexity: O(n * m) in the worst case, where n is the number of nodes in
sand m is the number of nodes int. This is because for each node ins, we might need to check if it matchest. - Space Complexity: O(h_s + h_t), where h_s is the height of
sand h_t is the height oft. This is due to the recursion stack.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_identical(s: TreeNode, t: TreeNode) -> bool:
if not s and not t:
return True
if not s or not t:
return False
if s.val != t.val:
return False
return (is_identical(s.left, t.left) and
is_identical(s.right, t.right))
def is_subtree(s: TreeNode, t: TreeNode) -> bool:
if not s:
return False
if is_identical(s, t):
return True
return (is_subtree(s.left, t) or
is_subtree(s.right, t))
Edge Cases Handled
- Empty
t: The function will correctly identify that an empty tree is a subtree of any tree. - Large Trees: The recursive approach handles large trees by breaking them down into smaller subproblems.
- Duplicate Values: The function correctly compares the structure and values, so duplicate values do not affect the result.