mock interview

class Solution {
    using n2t = array<Node*, 2>;
    n2t traverse(Node* node) {
        if (node == nullptr) return {nullptr, nullptr};
        auto r1 = traverse(node->left);
        auto r2 = traverse(node->right);
        if (r1[0] != nullptr) {
            r1[1]->right = node;
            node->left = r1[1];
        } else {
            node->left = nullptr;
        }

        if (r2[0] != nullptr) {
            node->right = r2[0];
            r2[0]->left = node;
        } else {
            node->right = nullptr;
        }

        return {r1[0] != nullptr ? r1[0] : node, r2[0] != nullptr ? r2[1] : node};
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) return root;
        auto ret = traverse(root);
        ret[0]->left = ret[1];
        ret[1]->right = ret[0];
        return ret[0];
    }
};