Answer to Question #297113 in C++ for Huma

Question

Write a function named mybstmirror() that takes a reference to the root node of a binary tree and creates

a new tree (with its own nodes) that is the mirror image of the original tree. For example: if root is a reference to the root of the tree on the left below, then the return value of mybstmirror(root) would

be a reference to the root of the tree on the right below.

Node mybstmirror(Node root)

Answer 1

#include <iostream>
#include <cstdlib>
using namespace std;


struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) { data = val;  left = right = nullptr; }
};


// Add a node to form a binary search tree
Node* add_bst(Node* root, int val) {
    if (!root) {
        return new Node(val);
    }
    if ( val < root->data) {
        root->left = add_bst(root->left, val);
    }
    else {
        root->right = add_bst(root->right, val);
    }
    return root;
}


// Print a tree
void print_bst(Node* root) {
    if (!root) {
        cout << "#";
        return;
    }
    cout << "(" << root->data << ": l=";
    print_bst(root->left);
    cout << ", r=";
    print_bst(root->right);
    cout << ")";
}


// Mirror bst
Node* mybstmirror(Node* root) {
    if (!root) {
        return root;
    }
    Node* new_root = new Node(root->data);
    new_root->right = mybstmirror(root->left);
    new_root->left = mybstmirror(root->right);
    return new_root;
}


// Generate a tree of size n using random numbers
Node* generate_bst(int n) {
    Node* root = nullptr;


    for (int i=0; i<n; i++) {
        int x = rand() % 100;
        root = add_bst(root, x);
    }
    return root;
}


int main() {
    Node* bst = generate_bst(10);


    cout << "Original tree: " << endl;
    print_bst(bst);


    Node* mirror_bst = mybstmirror(bst);
    cout << endl << "Mirrored tree:" << endl;
    print_bst(mirror_bst);


    return 0;
}