> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/trees ]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/subtree-of-another-tree/]
> [up:: [[Leetcode MOC]]]
## Problem
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
**Constraints:**
- The number of nodes in the `root` tree is in the range `[1, 2000]`.
- The number of nodes in the `subRoot` tree is in the range `[1, 1000]`.
- `-10^4 <= root.val <= 10^4`
- `-10^4 <= subRoot.val <= 10^4`
## Solution
### Mine
#### Python
```python
# 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: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root:
return False
if not subRoot:
return True
if self.same_tree(root, subRoot):
return True
else:
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def same_tree(self, r: Optional[TreeNode], s: Optional[TreeNode]) -> bool:
if not r and not s:
return True
if r and s and r.val == s.val:
return self.same_tree(r.left, s.left) and self.same_tree(r.right, s.right)
return False
```
#### Rust
### LC's
## Things I Learned
## Scratchpad
marker for current root tree node, and marker for subRoot tree node.
Put roots in both.
BFS in root tree until current node matches current subRoot node, then immediately search next level for children (updating current node for subRoot). If there is a mismatch, go to current's sibling and continue. If not, and we match all nodes, then return true
Didn't use this approach. Instead I did this, following Neetcode's example:
- Created a function `same_tree()` - this recursively calls itself with the children of the root and subtree nodes provided to it, only returning `True` (thanks to the `and`) if all descendants match.
- In the main function, if `root` is None, return False (a tree can't be a subtree of nothing), if there is no subRoot, return True.
- Then, call `same_tree()` on root and subRoot, return True if True
- If there isn't a match, recursively call `isSubtree` on the left child and subRoot, as well as the right child and subRoot. These are joined with an `or` since only one needs to be True.