Flatten Binary Tree

• Time : O(n)
• Space : O(1)

#include <vector>
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* prv;
void travel(BinaryTree* node) {
	if(!node) return;
	travel(node->left);
	
	prv->right = node;
	node->left = prv;
	prv = node;
	travel(node->right);
}

BinaryTree *flattenBinaryTree(BinaryTree *root) {
  prv = new BinaryTree(-1);
	BinaryTree& dummy = *prv;
	travel(root);
	dummy.right->left = nullptr;
  return dummy.right;
}