binary tree to binary search tree

Question

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)

Answer 1

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.

Answer 2

pop(0) on a Python list is an \$O(n)\$ operation because it is really an array rather than a list, and all remaining elements are shifted back to fill the empty slot. Swapping left and right in your code would allow you to pop() from the end instead, which is \$O(1)\$.

Using pop(0) on all elements pushed the complexity of the whole operation to \$O(n ^ 2)\$.