Modify Binary Tree by replacing all nodes at even and odd levels by their nearest even or odd perfect squares respectively

#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    int data;

    struct Node *left, *right;

};

  

void LevelOrderTraversal(Node* root)

{

    

    if (root == NULL)

        return;

  

    

    

    queue<Node*> q;

  

    

    q.push(root);

  

    

    int lvl = 1;

  

    

    while (q.empty() == false) {

  

        

        

        int n = q.size();

  

        

        for (int i = 0; i < n; i++) {

  

            

            Node* node = q.front();

  

            

            double num = sqrt(node->data);

            int x1 = floor(num);

            int x2 = ceil(num);

  

            

            if (x1 == x2) {

  

                

                

                if ((lvl & 1) && !(x1 & 1)) {

  

                    int num1 = x1 - 1, num2 = x1 + 1;

  

                    node->data

                        = (abs(node->data - num1 * num1)

                           < abs(node->data - num2 * num2))

                              ? (num1 * num1)

                              : (num2 * num2);

                }

  

                

                

                if (!(lvl & 1) && (x1 & 1)) {

  

                    int num1 = x1 - 1, num2 = x1 + 1;

  

                    node->data

                        = (abs(node->data - num1 * num1)

                           < abs(node->data - num2 * num2))

                              ? (num1 * num1)

                              : (num2 * num2);

                }

            }

  

            

            

            else {

                if (lvl & 1)

                    node->data

                        = (x1 & 1) ? (x1 * x1) : (x2 * x2);

                else

                    node->data

                        = (x1 & 1) ? (x2 * x2) : (x1 * x1);

            }

  

            

            

            cout << node->data << " ";

            q.pop();

  

            

            if (node->left != NULL)

                q.push(node->left);

  

            

            if (node->right != NULL)

                q.push(node->right);

        }

  

        

        lvl++;

        cout << endl;

    }

}

  

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  

int main()

{

    

    Node* root = newNode(5);

    root->left = newNode(3);

    root->right = newNode(2);

    root->right->left = newNode(16);

    root->right->right = newNode(19);

  

    LevelOrderTraversal(root);

  

    return 0;

}

Let's block ads! (Why?)