**source:**https://leetcode.com/problems/same-tree**C/C++**

**Solution to LeetCode**problem

**100**.

**Same Tree**.

## 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.

## Examples

**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]`

. `-10`

^{4}<= Node.val <= 10^{4}

## Solution

We will explore both trees simultaneously with a BFS (Breadth First Search) algorithm.

- Insert the root nodes to the queue using
`pair<TreeNode*, TreeNode*>`

. - While the queue has nodes:
- If one node exists, but the other no, return
`false`

. - If both nodes exist:
- If their values are different, return
`false`

. - Insert to the queue the pointers to the left and right of each node.

- If their values are different, return
- Pop the first element (pair of nodes) from the queue

- If one node exists, but the other no, return
- Return
`true`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<pair<TreeNode *, TreeNode *>> bfs;
bfs.push({p, q});
TreeNode *a;
TreeNode *b;
while (!bfs.empty()) {
a = bfs.front().first;
b = bfs.front().second;
if ((!a && b) || (a && !b))
return false;
if (a && b) {
if (a->val != b->val)
return false;
bfs.push({a->left, b->left});
bfs.push({a->right, b->right});
}
bfs.pop();
}
return true;
}
};