binary tree to binary search tree

Today I had an interview where I was asked to solve "Given an binary tree, convert it to binary search tree in minimum time, space complexity".

I wrote this code, but got the feedback that complexity could be improved without using sort and without using external storage.

How to do it?

##code goes below##:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(root,arr):
    if root is None:
        return
    inorder(root.left, arr)
    arr.append(root.data)
    inorder(root.right, arr)

def binary_to_bst(root, arr):
    if root is None:
        return
    binary_to_bst(root.left, arr)
    root.data = arr.pop(0)
    binary_to_bst(root.right, arr)

root = Node(4)
root.left = Node(2)
root.right = Node(1)
root.left.left = Node(5)
root.left.right  = Node(7)
root.right.left = Node(12)
arr = []
inorder(root,arr)
arr.sort()
binary_to_bst(root, arr)

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.

StackExchange Code Review Q#161187, answer score: 4