void flattenRec(BinaryTree* root, BinaryTree*& head, BinaryTree*& tail)
{
    if(!root) return;
    BinaryTree* leftHead=NULL, leftTail=NULL;
    if(root->left!=NULL){
        flattenRec(root->left, leftHead, leftTail);
        root->left=leftTail;
        leftTail->right=root;
    }

    BinaryTree* rightHead=NULL, rightTail=NULL;
    if(root->right!=NULL){
        flattenRec(root->right, rightHead, rightTail);
        root->right=rightHead;
        rigthHead->left=root;
    }

    head=leftHead? leftHead : root;
    tail=rightTail? rightTail : root;
}

void flatten(BinaryTree* root)
{
    BinaryTree* head;
    BinaryTree* tail;

    flattenRec(root, head, tail);

    head->left=tail;
    tail->right=head;
}