-
Notifications
You must be signed in to change notification settings - Fork 148
/
Structurally identical.cpp
87 lines (68 loc) · 2.48 KB
/
Structurally identical.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
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
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
*/
/************************************************************
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];
}
}
};
************************************************************/
#include<vector>
bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {
// Write your code here
//corner case
if(root1 == NULL and root2 == NULL) {
return true;
}
if((root1 == NULL and root2 != NULL) or (root1 != NULL and root2 == NULL)) {
return false;
}
if((root1 -> data != root2 -> data) or (root1 -> children.size() != root2 -> children.size())) {
return false;
}
bool flag = true;
for(int i = 0; i < root1 -> children.size(); i++) {
flag = areIdentical(root1 -> children[i], root2 -> children[i]);
if(!flag) {
return false;
}
}
if(root1 -> data == root2 -> data) {
return true;
} else {
return false;
}
}