**Problem Statement:**

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].
- -104 <= Node.val <= 104

**Solution:**

**Algorithm:**

- If both the trees are empty, return true.
- If both the trees are not empty, then check if the root node of both the trees are same.
- If the root node of both the trees are same, then recursively check for the left and right subtree of both the trees.
- If the root node of both the trees are not same, then return false.
- If the left subtree of both the trees are not same, then return false.
- If the right subtree of both the trees are not same, then return false.
- If all the above conditions are satisfied, then return true.

**Code:**

```
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null)
return true;
if (p == null || q == null)
return false;
if (p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
```

**Time Complexity:**

O(n)

**Space Complexity:**

O(n)

## Top comments (0)