# LeetCode: 100. Same Tree

**The 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**

```
Input: p = [1,2,3], q = [1,2,3]
Output: true
```

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
bool inorder(TreeNode* p, TreeNode* q){
if(p == NULL && q == NULL) return true;
else if(p == NULL && q != NULL) return false;
else if(p != NULL && q == NULL) return false;
else if(p->val != q->val) return false;
return inorder(p->left, q->left) && inorder(p->right, q->right);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
return inorder(p, q);
}
```

This code defines two functions: `inorder`

and `isSameTree`

, both of which are used to determine if two binary trees are the same.

`bool inorder(TreeNode* p, TreeNode* q) {`

- The
`inorder`

function takes two pointers to`TreeNode`

objects,`p`

and`q`

, as input and returns a boolean value (`true`

or`false`

). - It aims to perform an in-order traversal of two binary trees simultaneously while comparing their corresponding nodes.

`if (p == NULL && q == NULL) return true;`

- This is the base case for the recursion. It checks if both
`p`

and`q`

are`NULL`

, meaning we've reached the end of both trees, and returns`true`

to indicate that the traversal so far has been equal.

`else if (p == NULL && q != NULL) return false;`

4. `else if (p != NULL && q == NULL) return false;`

- These two conditions handle the case where one of the nodes is
`NULL`

while the other is not, indicating a mismatch in the tree structures. In this case, the function returns`false`

as the trees are not the same.

`else if (p->val != q->val) return false;`

- If both
`p`

and`q`

are not`NULL`

but have different values, it means the nodes at the current positions in the two trees are not the same. In this case, the function returns`false`

.

`return inorder(p->left, q->left) && inorder(p->right, q->right);`

- This line is where the recursion happens. It recursively calls the
`inorder`

function on the left subtrees and right subtrees of the input trees`p`

and`q`

. It uses the logical AND (`&&`

) operator to combine the results of these recursive calls. - This ensures that both the left subtrees and right subtrees of the trees
`p`

and`q`

must be the same for the entire trees to be considered the same.

`bool isSameTree(TreeNode* p, TreeNode* q) {`

- The
`isSameTree`

function simply calls the`inorder`

function with the input trees`p`

and`q`

, which initiates the comparison process.

Overall, these functions work together to determine if two binary trees (`p`

and `q`

) are the same by performing an in-order traversal and comparing corresponding nodes.