Convert a Binary Tree into its Mirror Tree | Iterative CPP program to convert a Binary Tree to its mirror ; A binary tree node has data , pointer to left child and a pointer to right child ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Change a tree so that the roles of the left and right pointers are swapped at every node . So the tree ... 4 / \ 2 5 / \ 1 3 is changed to ... 4 / \ 5 2 / \ 3 1 ; Do BFS . While doing BFS , keep swapping left and right children ; pop top node from queue ; swap left child with right child ; push left and right children ; Helper function to print Inorder traversal . ; Driver program to test mirror ( ) ; Print inorder traversal of the input tree ; Convert tree to its mirror ; Print inorder traversal of the mirror tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left ; struct Node * right ; } ; struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } void mirror ( Node * root ) { if ( root == NULL ) return ; queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { Node * curr = q . front ( ) ; q . pop ( ) ; swap ( curr -> left , curr -> right ) ; if ( curr -> left ) q . push ( curr -> left ) ; if ( curr -> right ) q . push ( curr -> right ) ; } } void inOrder ( struct Node * node ) { if ( node == NULL ) return ; inOrder ( node -> left ) ; cout << node -> data << " ▁ " ; inOrder ( node -> right ) ; } int main ( ) { struct Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; cout << " Inorder traversal of the " STRNEWLINE TABSYMBOL TABSYMBOL TABSYMBOL " constructed tree is " ; inOrder ( root ) ; mirror ( root ) ; cout << " Inorder traversal of the " STRNEWLINE TABSYMBOL TABSYMBOL " mirror tree is " ; inOrder ( root ) ; return 0 ; }