Right Sibling Tree Time : O(n) Space : O(2^d) 123456789101112131415161718192021222324252627282930313233343536373839#include <vector>#include <queue>using namespace std;// This is the class of the input root. Do not edit it.class BinaryTree {public: int value; BinaryTree *left = nullptr; BinaryTree *right = nullptr; BinaryTree(int value);};BinaryTree *rightSiblingTree(BinaryTree *root) { queue<BinaryTree*> q; q.push(root); while(true) { bool pushed = false; int sz = q.size(); while(sz--) { auto node = q.front(); q.pop(); if(node == nullptr) { q.push(nullptr); } else { if(!node->left and !node->right) q.push(nullptr); else { q.push(node->left); q.push(node->right); pushed = true; } node->right = nullptr; if(sz) node->right = q.front(); } } if(!pushed) break; } return root;}