Question

Write a function named mirror_tree that accepts a pointer to the root of a binary tree of integers. Your function should rearrange the nodes into a mirror tree of the original tree. The mirror tree has the left and right subtrees reversed for each node.

Constraints: You must implement your function recursively and without using loops. Do not construct any new BST objects in solving this problem (though you may create as many NODE* pointer variables as you like). Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).

Assume that you are using the NODE structure as defined below:

struct NODE {
int Key;
NODE* Left;
NODE* Right;
};

If you run mirror_tree on a BST, is your new tree still a BST?

Code to edit:

/ util.h

#include <iostream>
#include "bst.h"
using namespace std;

// mirror_tree:
//
// Your function should rearrange the nodes into a mirror tree
// of the original tree. The mirror tree has the left and right
// subtrees reversed for each node.
//
void mirror_tree(NODE* node) {
// TO DO: Write this function.
}

Answer 1

// C++ program to convert a binary tree 
// to its mirror 
#include<bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer 
to left child and a pointer to right child */
struct Node 
{ 
        int data; 
        struct Node* left; 
        struct Node* right; 
}; 

/* Helper function that allocates a new node with 
the given data and NULL left and right pointers. */
struct Node* newNode(int data) 
{ 
        struct Node* node = (struct Node*) 
                                                malloc(sizeof(struct Node)); 
        node->data = data; 
        node->left = NULL; 
        node->right = NULL; 
        
        return(node); 
} 


/* 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 
*/
void mirror(struct Node* node) 
{ 
        if (node == NULL) 
                return; 
        else
        { 
                struct Node* temp; 
                
                /* do the subtrees */
                mirror(node->left); 
                mirror(node->right); 
        
                /* swap the pointers in this node */
                temp     = node->left; 
                node->left = node->right; 
                node->right = temp; 
        } 
} 

/* Helper function to print 
Inorder traversal.*/
void inOrder(struct Node* node) 
{ 
        if (node == NULL) 
                return; 
        
        inOrder(node->left); 
        cout << node->data << " "; 
        inOrder(node->right); 
} 


// Driver Code 
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); 
        
        /* Print inorder traversal of the input tree */
        cout << "Inorder traversal of the constructed"
                << " tree is" << endl; 
        inOrder(root); 
        
        /* Convert tree to its mirror */
        mirror(root); 
        
        /* Print inorder traversal of the mirror tree */
        cout << "\nInorder traversal of the mirror tree"
                << " is \n"; 
        inOrder(root); 
        
        return 0; 
}