Subtree of Another Tree
- 1 min read
- LC-Easy
- Binary Tree
3 years ago
Solution
- Use the same function from Same Tree to check if two subtrees are equal
- Just recur down the root tree with Depth-first Search and call the same tree function for each node.
- Edge cases:
- If subroot is null, return true. Because an empty tree is considered a subtree of any tree
- If root is null, return False. This condition is after the first condition, and it means subtree wasn't empty, and tree was empty. They cannot be equal, so return False
| Time | Space | Explanation |
|---|---|---|
O(s * t) | O(log(s) * log(t)) |
def are_equal(self, p, q):
if not p and not q:
return True
if (not p and q) or (not q and p):
return False
return p.val == q.val and self.are_equal(p.left, q.left) and self.are_equal(p.right, q.right)
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not subRoot:
return True
if not root:
return False
if self.are_equal(root, subRoot):
return True
if self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot):
return True
return False