Structurally identical

 

Given two generic trees, return true if they are structurally identical. Otherwise return false.

Structural Identical
If the two given trees are made of nodes with the same values and the nodes are arranged in the same way, then the trees are called identical.
Input format :
The first line of input contains data of the nodes of the first tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.  
The following line of input contains data of the nodes of the second tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.
Output format :
The first and only line of output contains true, if the given trees are structurally identical and false, otherwise.
Constraints:
Time Limit: 1 sec
Sample Input 1 :
10 3 20 30 40 2 40 50 0 0 0 0 
10 3 20 30 40 2 40 50 0 0 0 0
Sample Output 1 :
true/************************************************************
Following is the structure for the TreeNode class

template <typename T>
class TreeNode {
public:
T data;
vector<TreeNode<T>*> children;
TreeNode(T data) {
this->data = data;
}
~TreeNode() {
for (int i = 0; i < children.size(); i++) {
delete children[i];
}
}
};

************************************************************/

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {
// Write your code here
bool p;
if(root1==NULL&&root2==NULL)
{
return true;
}
else if((root1!=NULL&&root2==NULL)||(root2!=NULL&&root1==NULL))
{
return false;
}
if(root1->data==root2->data)
{
if(root1->children.size()==root2->children.size())
{
if(root1->children.size()==0)
{
return true;
}
for(int i=0;i<root1->children.size();i++)
{
if(root1->children[i]->data!=root2->children[i]->data)
{
return false;
}
}
for(int i=0;i<root1->children.size();i++)
{
p=areIdentical(root1->children[i],root2->children[i]);
}
}
else
{
return false;
}
}
else
{
return false;
}
return p;
}
Sample Input 2 :
10 3 20 30 40 2 40 50 0 0 0 0 
10 3 2 30 40 2 40 50 0 0 0 0
Sample Output 2:
false



Comments

Post a Comment

Popular posts from this blog

Code : All connected components

  Given an undirected graph G(V,E), find and print all the connected components of the given graph G. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. 3. You need to take input in main and create a function which should return all the connected components. And then print them in the main, not inside function. Print different components in new line. And each component should be printed in increasing order (separated by space). Order of different components doesn't matter. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two space separated integers, that denote that there exists an edge between vertex a and b. Output Format : Print different components in new line. And each component should be printed in increasing order of vertices (separated by space). Order of different components doesn't matter....
Read more

Coding Ninjas

  Given a NxM matrix containing Uppercase English Alphabets only. Your task is to tell if there is a path in the given matrix which makes the sentence “CODINGNINJA” . There is a path from any cell to all its neighbouring cells. For a particular cell, neighbouring cells are those cells that share an edge or a corner with the cell. Input Format : The first line of input contains two space separated integers N and M, where N is number of rows and M is the number of columns in the matrix. Each of the following N lines contain M characters. Please note that characters are not space separated. Output Format : Print 1 if there is a path which makes the sentence “CODINGNINJA” else print 0. Constraints : 1 <= N <= 1000 1 <= M <= 1000 Time Limit: 1 second Sample Input 1: 2 11 CXDXNXNXNXA XOXIXGXIXJX Sample Output 1: 1 bool hasPath ( vector < vector < char >> & board , int n , int m ) { // Write your code here. } #include < iostream > #include ...
Read more