Right Sibling Tree

• Time : O(n)
• Space : O(2^d)

c++

#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;
}