Mirror a Binary Tree without recursion

Question

I am trying to mirror the binary tree without recursive methods by using two queues and a binary tree which I have created. Following is the function which i have used. root is the pointer to the root node of the original binary tree and mirrior_root is of a mirrored binary tree. The error seems to be lies in the logic part !

Help would be appreciated !

#include<iostream>
#include<queue>

using namespace std;

class Node
{
    public:
        Node *lchild;
        int data;
        Node *rchild; 
};

class Tree
{
    public:
        Node *root;
        Node *mirror_root;
        Tree()
        {
            root = NULL;
        }
        void create_Tree()
        {
            Node *p;
            Node *t;
            int x;
            queue <Node *> q;

            root = new Node ;
            cout << "Enter the data you want to insert in root";
            cin >> x;
            root->data = x;
            root->lchild = root ->rchild = NULL;
            q.emplace(root);

            while(! q.empty())
            {
                p = q.front();
                q.pop();

                cout << "Enter the left child of " << p->data << ":";
                cin >> x;
                if(x != -1)
                {
                    t= new Node;
                    t->data = x;
                    t->lchild = t->rchild = NULL;
                    p->lchild = t;
                    q.emplace(t);
                }
                cout << "Enter the right child of " << p->data << ":";
                cin >> x;
                if(x != -1)
                {
                    t= new Node;
                    t->data = x;
                    t->lchild = t->rchild = NULL;
                    p->rchild = t;
                    q.emplace(t);
                }
            }

        }
        void Preorder(Node *p)
        {
            if(p)
            {
                cout << p->data << " " ;
                Preorder(p->lchild);
                Preorder(p->rchild);
            }
        }
        void Level_order(Node *p)
        {
            queue <Node *> q;
            q.emplace(p);
            cout << p->data << " " ;

            while(!q.empty())
            {
                p = q.front();
                q.pop();

                if(p->lchild)
                {
                    cout << p->lchild->data << " ";
                    q.emplace(p->lchild);
                }
                if(p->rchild)
                {
                    cout << p->rchild->data << " ";
                    q.emplace(p->rchild);
                }
            }
        }
        void mirror_tree(Node *p)
        {
            Node *mirror_root;
            Node *t;
            Node *k;

            queue <Node *> q_root;
            queue <Node *> q_mirror;

            mirror_root = new Node;
            mirror_root->data = p->data;
            mirror_root->lchild = mirror_root->rchild = NULL;

            t=mirror_root;

            q_root.emplace(p);
            q_mirror.emplace(t);

            while(!q_root.empty())
            {
                p=q_root.front();
                q_root.pop();

                t = q_mirror.front();
                q_mirror.pop();

                if(p->lchild)
                {
                    k = new Node;
                    k->data = p->lchild->data;
                    k->lchild = k->rchild = NULL;
                    t->rchild = k;
                    q_root.emplace(p->lchild);
                    q_mirror.emplace(t->rchild);

                }

                if(p->rchild)
                {
                    k = new Node;
                    k->data = p->rchild ->data;
                    k->lchild = k->rchild = NULL;
                    t->lchild = k;
                    q_root.emplace(p->rchild);
                    q_mirror.emplace(t->lchild);
                }
            }
        }
};

int main()
{
    Tree bt;
    bt.create_Tree();
    bt.mirror_tree(bt.root);

    cout << "Level order of mirrored binary tree is  : ";
    bt.Level_order(bt.mirror_root);

}

Here is input and output

Enter the data you want to insert in root: 5

Enter the left child of 5:6

Enter the right child of 5:7

Enter the left child of 6:8

Enter the right child of 6:9

Enter the left child of 7:10

Enter the right child of 7:11

Enter the left child of 8:-1

Enter the right child of 8:-1

Enter the left child of 9:-1 Enter the right child of 9:-1

Enter the left child of 10:-1

Enter the right child of 10:-1

Enter the left child of 11:-1

Enter the right child of 11:-1

Level order of mirrored binary tree is : 7769539

Output which i expected is

Level order of mirrored binary tree is 5 7 6 11 10 9 8

What exactly is the problem? Can you provide input & output to illustrate the issue? — trincot
mirror_tree doesn't have any side effects. Apart from leaked memory, it's a very elaborate no-op. Did you mean to perhaps return mirror_root, or in some other way convey it to the caller? — Igor Tandetnik
What I am actually doing is giving a binary tree as input and tend to store the mirror of the input binary tree in mirror_root(the mirror_root would store the root of the mirrored binary tree using which we can access the whole mirrored binary tree) . — Prameet Upadhyay
The code you provided is not outputting anything... I don't see the connection with your provided input/output with the code. — trincot
I have just provided the function which returns a mirror_root. — Prameet Upadhyay

trincot trincot · Accepted Answer · 2020-10-19T10:41:05

The problem is that you declare Node *mirror_root as a local variable in mirror_tree, while you want the code to give a value to the class member with the same name.

So remove that line from the mirror_tree function.

Mirror a Binary Tree without recursion

1 Answers