3
\$\begingroup\$

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)
\$\endgroup\$
  • 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
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.