struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/**
 * @param n   current node
 * @param pre previous node in pre-order traversal
 */
void flatten(TreeNode *n, TreeNode *&pre) {
    if (n == NULL) return;

    if (pre != NULL) {
        pre->right = n;
    }

    pre = n;
    TreeNode *rChild = n->right; //reserve right child in case it pointer to flatten node
    flatten(n->left, pre);
    n->left = NULL; //clear left node
    flatten(rChild, pre);
}

void flatten(TreeNode *root) {
    TreeNode *pre = NULL;
    flatten(root, pre);
}