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:
    inorder(root.left, arr)
    inorder(root.right, arr)

def binary_to_bst(root, arr):
    if root is None:
    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 = []
binary_to_bst(root, arr)
  • 1
    \$\begingroup\$ You describe the task as "Given an binary tree, convert it to a binary search tree." Now, a binary tree is unsorted (in general), but a binary search tree is sorted, so this task can't be done any faster than sorting the keys, and sorting arbitrary keys takes \$Θ(n\log n)\$. So I wonder if perhaps you haven't quite described the problem fully? \$\endgroup\$ – Gareth Rees Apr 19 '17 at 19:28

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.

  • \$\begingroup\$ can we implement simple binary tree? if yes then how? is there any source code? because as I noticed that the tree goes to one side of the root(parent). \$\endgroup\$ – Asif Mushtaq Apr 3 '18 at 12:29

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)\$.


Your Answer

