Modify a Binary Tree by shifting all nodes to as far right as possible

#include <bits/stdc++.h>

using namespace std;

  

struct TreeNode {

    int val = 0;

    TreeNode* left;

    TreeNode* right;

  

    

    TreeNode(int x)

    {

        val = x;

        left = right = NULL;

    }

};

  

void printTree(TreeNode* root)

{

    if (!root)

        return;

  

    

    printTree(root->left);

  

    

    cout << root->val << " ";

  

    

    printTree(root->right);

}

  

TreeNode* shiftRight(TreeNode* root)

{

  

    

    if (!root)

        return NULL;

  

    stack<TreeNode*> st;

    queue<TreeNode*> q;

  

    

    if (root->right)

        q.push(root->right);

  

    root->right = NULL;

  

    

    if (root->left)

        q.push(root->left);

  

    root->left = NULL;

  

    

    st.push(root);

  

    while (!q.empty()) {

  

        

        

        int n = q.size();

        stack<TreeNode*> temp;

  

        

        

        while (n--) {

  

            

            if (!st.top()->right)

  

                

                

                st.top()->right = q.front();

  

            

            else {

  

                

                st.top()->left = q.front();

  

                

                

                st.pop();

            }

  

            

            if (q.front()->right)

  

                

                q.push(q.front()->right);

  

            

            q.front()->right = NULL;

  

            

            if (q.front()->left)

  

                

                q.push(q.front()->left);

  

            

            q.front()->left = NULL;

  

            

            

            

            temp.push(q.front());

            q.pop();

        }

  

        while (!st.empty())

            st.pop();

  

        

        

        while (!temp.empty()) {

  

            st.push(temp.top());

            temp.pop();

        }

    }

  

    

    

    return root;

}

  

int main()

{

  

    TreeNode* root = new TreeNode(1);

    root->left = new TreeNode(2);

    root->right = new TreeNode(3);

    root->left->left = new TreeNode(4);

    root->left->right = new TreeNode(5);

    root->right->right = new TreeNode(6);

  

    

    root = shiftRight(root);

  

    

    printTree(root);

  

    return 0;

}

Let's block ads! (Why?)