# Determine if two trees are same in C++ – LeetCode Solution [Easy]

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 each identical node has the same value.

###### Pseudocode
1. Traverse the given binary trees rooted at root(p) and root(q) in a preorder fashion.
2. Do if p == NULL && q == NULL, return true
3. Else if either of the two is null not both,
ie p == NULL || q == NULL, return false
3. Traverse p->left && p->right and q->left && q->right
4. If info[p] and info[q] for (p and q) and also for (p->left and q->left) and (p->right and q->right) match equal respectively, return true
5. Else, return false 

Code Implementation

//
//  main.cpp
//  Same Tree
//
//  Created by Himanshu on 14/10/21.
//

#include <iostream>
#include <queue>
using namespace std;

struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;

return(Node);
}

bool checkIfSame(Node *p, Node *q) {
if (p == NULL && q == NULL) {
return true;
} else if (p == NULL || q == NULL) {
return false;
}
if (p->info == q->info && checkIfSame(p->left, q->left) &&
checkIfSame(p->right, q->right)) {
return true;
} else {
return false;
}

}

int main() {
Node *root = newNode(21);
root->left = newNode(30);
root->right = newNode(31);
root->right->left = newNode(40);
root->right->left->right = newNode(51);

Node *root1 = newNode(21);
root1->left = newNode(30);
root1->right = newNode(31);
root1->right->left = newNode(40);
root1->right->left->right = newNode(51);

Node *root2 = newNode(21);
root2->left = newNode(30);
root2->right = newNode(31);
root2->right->left = newNode(40);
root2->right->left->right = newNode(50);

cout<<"Are trees with root (root) and root (root1) are same?"<<endl;
if (checkIfSame(root, root1)) {
cout<<"Trees are same"<<endl;
} else {
cout<<"Trees are not same"<<endl;
}

cout<<"Are trees with root (root) and root (root2) are same?"<<endl;
if (checkIfSame(root, root2)) {
cout<<"Trees are same"<<endl;
} else {
cout<<"Trees are not same"<<endl;
}

return 0;
}



Output

Are trees with root (root) and root (root1) are same?
Trees are same
Are trees with root (root) and root (root2) are same?
Trees are not same

Time complexity: O(n) where n is the number of nodes in larger tree.

Here’s a working example: Ideone