I don't think that time complexity could be improved. An in-place approach is to flatten the tree into a list (the key is to reuse child pointers), and recreate the tree as BST. To flatten,

    def flatten(root):
        rightmost = get_rightmost(root)
        while root:
            rightmost.right = root.left
            rightmost = get_rightmost(root.left)
            root.left = None
            root = root.right

The time complexity of flattening is \$O(n\log n)\$, for a worst case of a complete tree.

To recreate,

    def list_to_bst(root):
        cursor = root
        while cursor:
            next = cursor.right
            cursor.right = None
            root = insert(root, cursor)
            cursor = next

insert is a standard (or balanced, if you want to go fancy) BST insertion. get_rightmost is trivial.

There is no recursion, so the space complexity is constant. The time complexity is bounded by insertion, that is in a \$O(n\log n)\$ ballpark.

I don't think that time complexity could be improved. An in-place approach is to flatten the tree into a list (the key is to reuse child pointers), and recreate the tree as BST. To flatten,

    def flatten(root):
        rightmost = get_rightmost(root)
        while root:
            rightmost.right = root.left
            rightmost = get_rightmost(root.left)
            root.left = None
            root = root.right

The time complexity of flattening is linear.

To recreate,

    def list_to_bst(root):
        cursor = root
        while cursor:
            next = cursor.right
            cursor.right = None
            root = insert(root, cursor)
            cursor = next

insert is a standard (or balanced, if you want to go fancy) BST insertion. get_rightmost is trivial.

There is no recursion, so the space complexity is constant. The time complexity is bounded by insertion, that is in a \$O(n\log n)\$ ballpark.

I don't think that time complexity could be improved. An in-place approach is to flatten the tree into a list (the key is to reuse child pointers), and recreate the tree as BST. To flatten,

    def flatten(root):
        rightmost = get_rightmost(root)
        while root:
            rightmost.right = root.left
            rightmost = get_rightmost(root.left)
            root.left = None
            root = root.right

The time complexity of flattening is linear (notice that at this step we don't care about ordering).

To recreate,

    def list_to_bst(root):
        cursor = root
        while cursor:
            next = cursor.right
            cursor.right = None
            root = insert(root, cursor)
            cursor = next

insert is a standard (or balanced, if you want to go fancy) BST insertion. get_rightmost is trivial.

There is no recursion, so the space complexity is constant. The time complexity is bounded by insertion, that is in a \$O(n\log n)\$ ballpark.

I don't think that time complexity could be improved. An in-place approach is to flatten the tree into a list (the key is to reuse child pointers), and recreate the tree as BST. To flatten,

    def flatten(root):
        rightmost = get_rightmost(root)
        while root:
            rightmost.right = root.left
            rightmost = get_rightmost(root.left)
            root.left = None
            root = root.right

The time complexity of flattening is \$O(n\log n)\$, for a worst case of a complete tree.

To recreate,

    def list_to_bst(root):
        cursor = root
        while cursor:
            next = cursor.right
            cursor.right = None
            root = insert(root, cursor)
            cursor = next

insert is a standard (or balanced, if you want to go fancy) BST insertion. get_rightmost is trivial.

There is no recursion, so the space complexity is constant. The time complexity is bounded by insertion, that is in a \$O(n\log n)\$ ballpark.