Algorithm: Check if Two Binary Trees are the Same
1. **Base Case**:
- If both nodes (`p` and `q`) are `null`, return `true` (both trees are empty and identical).
- If only one of the nodes is `null`, return `false` (one tree is empty, and the other is not).
- If the values of `p` and `q` are different, return `false` (trees are not identical).
2. **Recursive Case**:
- Recursively check if the left subtrees of `p` and `q` are the same.
- Recursively check if the right subtrees of `p` and `q` are the same.
- If both the left and right subtree checks return `true`, the trees are identical.
3. **Return the Final Result**:
- Combine the results of the left and right subtree checks using a logical `AND`.
---
### Code: Recursive Solution in Java
```java
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Base Case: Both nodes are null
if (p == null && q == null) {
return true;
}
// Base Case: One node is null or values are different
if (p == null || q == null || [Link] != [Link]) {
return false;
}
// Recursive Case: Check left and right subtrees
return isSameTree([Link], [Link]) && isSameTree([Link], [Link]);
}
}
```
---
### Example Walkthrough
#### Example Input:
`p = [1,2,3], q = [1,2,3]`
1. Start at root nodes (`p = 1`, `q = 1`):
- Both nodes are not `null` and have the same value.
- Check left subtree (`[Link] = 2`, `[Link] = 2`).
- Check right subtree (`[Link] = 3`, `[Link] = 3`).
2. Check left subtree (`[Link] = 2`, `[Link] = 2`):
- Both nodes are not `null` and have the same value.
- Check left subtree (`[Link] = null`, `[Link] = null`): **true**.
- Check right subtree (`[Link] = null`, `[Link] = null`): **true**.
- Both checks return `true`, so left subtree is identical.
3. Check right subtree (`[Link] = 3`, `[Link] = 3`):
- Both nodes are not `null` and have the same value.
- Check left subtree (`[Link] = null`, `[Link] = null`): **true**.
- Check right subtree (`[Link] = null`, `[Link] = null`): **true**.
- Both checks return `true`, so right subtree is identical.
4. Both left and right subtrees are identical, so return `true`.
---
### Notes to Include
- **Key Idea**: The algorithm compares the structure and node values of both trees
recursively.
- **Base Cases**:
1. Both nodes are `null` → Trees are identical.
2. One node is `null` or values are different → Trees are not identical.
- **Recursive Check**:
- Ensure both left and right subtrees are identical.
- **Time Complexity**: \(O(n)\), where \(n\) is the number of nodes in the smaller tree.
- **Space Complexity**: \(O(h)\), where \(h\) is the height of the tree, due to recursion.
This algorithm is efficient, concise, and directly solves the problem requirements.