> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/trees]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/same-tree/description/]
> [up:: [[Leetcode MOC]]]
## Problem
Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
**Example 1:**
**Input:** p = [1,2,3], q = [1,2,3]
**Output:** true
**Example 2:**
**Input:** p = [1,2], q = [1,null,2]
**Output:** false
**Example 3:**
**Input:** p = [1,2,1], q = [1,1,2]
**Output:** false
**Constraints:**
- The number of nodes in both trees is in the range `[0, 100]`.
- `-10e4 <= Node.val <= 10e4`
## Solution
### Mine
#### Python
```python
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
p_stack = [p]
q_stack = [q]
while q_stack and p_stack:
current_p = p_stack.pop()
current_q = q_stack.pop()
if (current_p is None and current_q is not None) or (current_p is not None and current_q is None):
return False
if current_p is None and current_q is None:
continue
if current_p.val != current_q.val:
return False
p_stack.extend([current_p.left, current_p.right])
q_stack.extend([current_q.left, current_q.right])
return True
```
Runtime:
37 ms
Beats 66.85%
Memory:
16.3 MB
Beats
30.42%
#### Rust
### Neetcode's
Recursive solution that doesn't require stacks
```python
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if p and q and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
```
Runtime: 42ms
Beats 27.17%of users with Python3
Memory:
16.26MB
Beats 65.14%of users with Python3
## Things I Learned
## Scratchpad
I think we could do DFS or BFS, and load all values into their own list and then compare lists.
However, to reduce space complexity, I think we could just simultaneously traverse the trees (maybe) and at each node check that the values are equal.
Did this, doing so though you maintain two stacks.