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