class Solution {
public:
    TreeNode* traverse(TreeNode* root) {
        if(root == nullptr) return nullptr;
        if(root->left == nullptr && root->right == nullptr) {
            return root;
        }
        TreeNode* leftTail = traverse(root->left);
        TreeNode* rightTail = traverse(root->right);

        if(leftTail != nullptr) {
            leftTail->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }

        return rightTail != nullptr ? rightTail : leftTail;
    }

    void flatten(TreeNode* root) {
        if(root == nullptr) return;
        traverse(root);
    }
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == nullptr) return;
        
        TreeNode* node = root;

        while(node != nullptr) {

            if(node->left != nullptr) {
                TreeNode* rightmost = node->left;
                // find rightmost
                while(rightmost->right != nullptr) {
                    rightmost = rightmost->right;
                }

                rightmost->right = node->right;
                node->right = node->left;
                node->left = nullptr;
            }
            node = node->right;
        }
    }
};