C++  Implementation

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    Node* left,*right;
    Node(int k)
    {
        data=k;
        left=right=NULL;
    }
};

Node* solve(Node* root)
{
    queue<Node*>q;
    q.push(root);
    while(!q.empty())
    {
        int sz=q.size();
        queue<Node*>parent;
        queue<Node*>child;
        queue<Node*>del;
        for(int i=0;i<sz;++i)
        {
            Node* curr=q.front();
            q.pop();
            parent.push(curr);
            del.push(curr);
            if(curr->right)
            {
                child.push(curr->right);
                q.push(curr->right);
            }
            if(curr->left)
            {
                child.push(curr->left);
                q.push(curr->left);
            } 
        }
        
        while(!del.empty())
        {
            Node* curr=del.front();
            del.pop();
            if(curr->left)
                curr->left=NULL;
            if(curr->right)
                 curr->right=NULL;
        }
        
        while(!parent.empty() && !child.empty())
        {
            Node* par=parent.front();
            parent.pop();
            Node* rigt=child.front();
            child.pop();
            par->right=rigt;
            if(child.size()>0)
            {
                Node* lft=child.front();
                child.pop();
                par->left=lft;
            }
        }
      
    }
      return root;
}

void print(Node* root)
{
    if(!root)
    {
        cout<<"NULL"<<" ";
        return ;
    }
    print(root->right);
    print(root->left);
    cout<<root->data<<" ";
}

int main()
{
    Node* root=new Node(10);
    root->left=new Node(4);
    root->right=new Node(15);
    root->right->right=new Node(16);
    root->right->right->left=new Node(13);
    root->left->left=new Node(1);
    root->left->right=new Node(20);
    root->left->right->right=new Node(11);
    root->left->right->left=new Node(7);
    root=solve(root);
    print(root);
    return 0;
}