C Program to Check if Two Trees are Mirror

This C Program checks whether a tree and its mirror image are same.

Here is source code of the C Program to check whether a tree and its mirror image are same. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Check whether a Tree and its Mirror Image are same
  3.  *                        50                               50
  4.  *                       /  \                             /  \
  5.  *                      20     30                        30   20
  6.  *  Sample Tree<------ /  \                                  /  \   ----------> Mirror image
  7.  *                    70      80                            80   70
  8.  *                   /  \    \                             /    /  \  
  9.  *                  10  40     60                        60   40   10
  10.  *                             (50,20,30,70,80,10,40,60)                                  
  11.  */
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. struct btnode {
  16.     int value;
  17.     struct btnode * l;
  18.     struct btnode * r;
  19. };
  20.  
  21. typedef struct btnode bt;
  22.  
  23. bt *root,*temp;
  24. bt *new;
  25. int c;
  26.  
  27. bt * create_node();
  28. void display(bt *);
  29. bt * construct_tree();
  30. void mirror_image(bt *);
  31. int compare(bt *,bt *);
  32.  
  33. void main()
  34. {
  35.     root = construct_tree();
  36.     display(root);
  37.     temp = construct_tree();
  38.     mirror_image(temp);
  39.     printf("\n mirror image:\n");
  40.     display(temp);
  41.     c = compare(root,temp);
  42.     if (c)
  43.     {
  44.         printf("\nsame");
  45.     }
  46.     else
  47.     {
  48.         printf("\nnot same");
  49.     }
  50. }
  51.  
  52. /* creates new node */
  53. bt * create_node()
  54. {
  55.     new=(bt *)malloc(sizeof(bt));
  56.     new->l = NULL;
  57.     new->r = NULL;
  58. }
  59.  
  60. /* constructs the tree */
  61. bt * construct_tree()
  62. {
  63.     bt *list;
  64.  
  65.     list = create_node();
  66.     list->value = 50;
  67.     list->l = create_node();
  68.     list->l->value = 20;
  69.     list->r = create_node();
  70.     list->r->value = 30;
  71.     list->l->l = create_node();
  72.     list->l->l->value = 70;
  73.     list->l->r = create_node();
  74.     list->l->r->value = 80;
  75.     list->l->r->r = create_node();
  76.     list->l->r->r->value = 60;
  77.     list->l->l->l = create_node();
  78.     list->l->l->l->value = 10;
  79.     list->l->l->r = create_node();
  80.     list->l->l->r->value = 40;
  81.  
  82.     return list;    
  83. }
  84.  
  85. /* displays the tree using inorder */
  86. void display(bt * list)
  87. {
  88.     if (list == NULL)
  89.     {
  90.         return;
  91.     }
  92.     display(list->l);
  93.     printf("->%d", list->value);
  94.     display(list->r);
  95. }
  96.  
  97. /* creates mirror image of a tree */
  98. void mirror_image(bt * list)
  99. {
  100.     bt * temp1;
  101.  
  102.     if (list == NULL)
  103.     {
  104.         return;
  105.     }
  106.     temp1 = list->l;
  107.     list->l = list->r;
  108.     list->r = temp1;
  109.     mirror_image(list->l);
  110.     mirror_image(list->r);
  111. }
  112.  
  113. /* compares tree and its mirror image */
  114. int compare(bt *list, bt * list1)
  115. {
  116.     int d;
  117.     if (list == NULL && list1 == NULL)
  118.     {
  119.         return 1;
  120.     }
  121.     else if (list != NULL && list1 != NULL)
  122.     {
  123.         return(list->value == list1->value &&
  124.         compare(list->l, list1->l) &&
  125.         compare(list->r, list1->r));
  126.     }
  127.     else
  128.     {
  129.         return 0;
  130.     }
  131. }

 
 
           50                                   50
          /  \                                 /  \ 
        20     30                             30   20
       /  \                                          /  \  
     70       80                                    80   70
    /  \    \                                   /    /  \
   10    40     60                                   60   40   10
   (Given Tree)                                (Mirror)
$ cc tree7.c
$ ./a.out
->10->70->40->20->80->60->50->30
mirror image:
->30->50->60->80->20->40->70->10
not same
 
            50                                    50
           /  \                                  /  \
          50   50                               50   50     
        (Given Tree)                          (Mirror)
 
$ ./a.out
->50->50->50
mirror image:
->50->50->50
same

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.