C++ Program to Swap the Binary Search Tree at each node

C++ Program to Swap the Binary Search Tree at each node

Introduction

In this article we are going to do a small C++ code to Create a Binary Search Tree and Swap the left and right pointers at each node.

Problem Statement

Modify the BST such that the roles of the left and right pointers are swapped at every node.

Solution : 

To swap the whole tree , we have to swap the positions of left and right pointers at every node recursively . 
The C++ implementation of it is as below : 

#Code for Swapping the Binary Search Tree
Download the Code here

#include<iostream>
using namespace std;

class treeNode
{
public:
    int data;

    treeNode *left;

    treeNode *right;

public:

    treeNode *createNewNode(int val);

    void insertInTree(int val);

    void inorder(treeNode*);

    void swapTree(treeNode *);
   
};

treeNode *root = NULL;

int main()
{
    treeNode t;

    int choise ;

    int value,numberOfNodes;

    cout<<"Number of nodes present in Tree : ";

    cin>>numberOfNodes;

    for (int i = 0; i < numberOfNodes; i++)
    {
        cout<<"Enter the value : ";

        cin>>value;

        t.insertInTree(value);
    }

   

    do
    {
        cout<<"\n\t\t\t________Operations on Binary Search Tree_________\n";

        cout<<"\n\t\t\t  1.Insert new node in Tree\n";

        cout<<"\t\t\t  2.Swap Tree\n";

        cout<<"\t\t\t  3.Inorder Traversal\n";

        cout<<"\t\t\t  4.Exit\n";

        cout<<"Your choise : ";

        cin>>choise;

        switch(choise)

      {
            case 1:
                {
                    cout<<"Enter the value : ";

                    cin>>value;

                    t.insertInTree(value);
                }
            break;

            case 2:

                    t.swapTree(root);

                    cout<<"\t\t\tTree Swapped !\n";

            break;

            case 3:

                    cout<<"Inorder Traversal is : \n";

                    t.inorder(root);

            break;
           
        }

    }while(choise<4&&choise>0);


}



treeNode *treeNode:: createNewNode(int val)
{
    treeNode *temp = new treeNode;

    temp->data = val;

    temp->left = NULL;

    temp->right = NULL;

    return temp;
}

void treeNode :: insertInTree(int val)
{
    treeNode *parent ,*current = root;

    if (root==NULL)
    {
        root = createNewNode(val);
    }
    else
    {
        while(current!=NULL)
        {
            parent = current;

            if (val<current->data)

                current = current->left;
            else

                if (val>current->data)

                current = current->right;
        }

        if (val<parent->data)

            parent->left = createNewNode(val);

        else

            if (val>parent->data)

                parent->right = createNewNode(val);
    }

}




void treeNode :: inorder(treeNode *Root)
{
    treeNode *temp= Root;

    if(temp==NULL)
        return;

    inorder(temp->left);

    cout<<"\t"<<temp->data;

    inorder(temp->right);
}

void treeNode :: swapTree(treeNode *Root)
{
    treeNode *current = Root;

    if (current ==NULL)
    {
        return ;
    }

    treeNode *temp = current->right;

    current->right = current->left;

    current->left = temp;

    swapTree(current->left);

    swapTree(current->right);

}

Note :  This code is successfully compiled and run under Linux distribution Ubuntu 18.04 LTS environment .   

Output :

$ g++ swapBinary.cpp
$ ./a.out

Number of nodes present in Tree : 5
Enter the value : 20
Enter the value : 10
Enter the value : 30
Enter the value : 5
Enter the value : 35


            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Swap Tree
            3.Inorder Traversal
            4.Exit
Your choise : 3
Inorder Traversal is :
    5    10    20    30    35

            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Swap Tree
            3.Inorder Traversal
            4.Exit
Your choise : 2
            Tree Swapped !


            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Swap Tree
            3.Inorder Traversal
            4.Exit
Your choise : 3
Inorder Traversal is :
    35    30    20    10    5