Program 13TH in C++

PROBLEM STATEMENT :

Return true if two trees are same

SOLUTION:

#include <iostream.h>

#include <cstdio>

#include <queue.h>

#include <vector.h>

using namespace std;

struct node

{

int data;

vector<node*> children;

};

//checking by level order traversal

bool check_tree(node* n, node* m)

{

queue<node*> q1;

queue<node*> q2;

int curr_count=1;

int next_count=0;

q1.push(n);

q2.push(m);

while(!q1.empty() && !q2.empty())

{

node* val1=q1.front();

node* val2=q2.front();

q1.pop();

q2.pop();

curr_count--;

if(val1->data == val2->data)

{

int size1=val1->children.size();

if(size1 == val2->children.size())

{

for(int i=0; i <size1; i++)

{

q1.push(val1->children[i]);

q2.push(val2->children[i]);

next_count++;

}

if(curr_count == 0)

{

curr_count=next_count;

next_count=0;

}

}

else

{

return false;

}

}

else

{

return false;

}

}

return true;

}

int main()

{

node Node[10];

node Node1[10];

for(int i=0; i<10; i++)

{

Node[i].data=i*2;

Node1[i].data=i*2;

}

//arranging childrens in first tree

Node[0].children.push_back(&Node[1]);

Node[0].children.push_back(&Node[2]);

Node[1].children.push_back(&Node[3]);

Node[1].children.push_back(&Node[4]);

Node[1].children.push_back(&Node[5]);

Node[2].children.push_back(&Node[6]);

Node[2].children.push_back(&Node[7]);

Node[2].children.push_back(&Node[8]);

Node[3].children.push_back(&Node[9]);

//arranging children in second tree

Node1[0].children.push_back(&Node1[1]);

Node1[0].children.push_back(&Node1[2]);

Node1[1].children.push_back(&Node1[3]);

Node1[1].children.push_back(&Node1[4]);

Node1[1].children.push_back(&Node1[5]);

Node1[2].children.push_back(&Node1[6]);

Node1[2].children.push_back(&Node1[7]);

Node1[3].children.push_back(&Node1[8]);

Node1[3].children.push_back(&Node1[9]);

bool out=check_tree(Node,Node1);

if(out == true)

cout<<"\n\n Trees are same\n\n";

else

cout<<"\n\n Trees are not same\n\n";

}