bool function checks and returns if the (sub) trees are completely identical

Sep 19, 2021 at 5:40pm
closed account (Nwb4iNh0)
Im trying to create a bool function : The function checks and returns if the (sub) trees are completely identical. Ie. that both trees have exactly the same structure (corresponding nodes have the same occurrence of left and right children) and ID in the corresponding nodes.

I got feed back on this code which is when I call this bool function should be in this form identicalTree(root1, root2) in main section and here is correct, but the function should not be this form bool identicalTree(Node* root1, Node* root2), so I dont know where is the errors here??


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
  #include<bits/stdc++.h>


using namespace std;

struct Node {
  int ID;
  Node *left, *right;
};


bool identicalTree(Node* root1, Node* root2){
    
    // if both current nodes are not null
    // both of the current nodes should have same value
   // the left subtree of both the trees should also be identical
    // the right subtree of both the trees should also be identical

 if(root1 && root2) 
    {
     if(root1->ID == root2->ID && identicalTree(root1->left, root2->left) && identicalTree(root1->right, root2->right)) return true;
        return false;
    }
    
     // if both tree have current nodes as null nodes

    else if(!root1 && !root2) return true;
     return false;
}

//////////////////////////////////////

// create node 
Node* create(int ID){
  Node* tmp = new Node();
  tmp->ID = ID;
  tmp->left = tmp->right = NULL;
  return tmp;
}

/////////////////////////////////
int main()
{
  //sub tree 1
  Node* root1 = create(4);
  root1->left = create (6);
  root1->left->right = create (1);
  root1-> left ->right->left = create (5);
  root1-> left->left = create (2);
  root1-> left ->left-> right = create (3);
//sub tree 2
  Node* root2 = create(4);
  root2->right= create (6);
  root2->right-> right= create (2);
  root2->right-> right->left = create (3);
  root2->right->left = create (1);
  root2->right->left->right =create (5);  

  cout<<(identicalTree(root1, root2) ? "Ye" : "No");
}
Sep 19, 2021 at 5:53pm
The only suggestion I can make is that the arguments should be const.
 
bool identicalTree(const Node* root1, const Node* root2)

Sep 20, 2021 at 9:05am
L27, 28 can be simplified as:

 
return !root1 && !root2;


and similar for L21, 22

Node can be changed to simplify create:

1
2
3
4
5
6
7
8
9
10
struct Node {
    int ID {};
    Node *left {}, *right {};

Node(int i) : ID(i) {}
};

Node* create(int ID) {
  return new Node(ID);
}

Last edited on Sep 20, 2021 at 9:06am
Sep 20, 2021 at 9:09am
#include<bits/stdc++.h>

This is a non standard header and you should never use it in your code.
Sep 20, 2021 at 2:45pm
the feedback seems picky... the best way to do this seems like setting up == operator on node
Last edited on Sep 20, 2021 at 2:45pm
Topic archived. No new replies allowed.