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)

• Gareth Rees: 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?
• greybeard: I find got the feedback that complexity could be improved without using sort and without using external storage interesting in an interview context: that would require the interviewer to spot the oversight causing o(n log n) time, and to know how to do RB or AVL trees without additional storage (as well as that Python allows object morphing for the way I think possible).

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.

• Asif Mushtaq: 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).

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

• greybeard: Swapping left and right in your code would allow you to pop() as would using arr.sort(reverse=True)