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 = Nonedef 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)
binary tree to binary search tree
python;tree;binary search
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.rightThe 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 = nextinsert 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.