Convert a Binary Tree to Doubly Linked List
Algorithm: because of the recursion, it still doesn't qualify as in-place. Consider a variation on a Morris traversal theme.



The calls to first() and last() are detrimental to the performance. Meanwhile, the callee already computed them. Consider returning a (fake) node pointing the beginning and the end of the flattened subtree, along the lines

    left = flatten(root.left);
    right = flatten(root.right);

    left.right.next = root;
    root.left = left.right;

    right.left.left = root;
    root.right = right.left;

    return Node(left.left, right.right);


There is only \$O(h)\$ Nodes to exist at any given moment, so the space complexity is not compromised.