# binary tree to binary search tree

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)

• 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? Apr 19, 2017 at 19:28
• 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). Jan 28, 2020 at 11:29

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.

• 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). Apr 3, 2018 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)$.

• Swapping left and right in your code would allow you to pop() as would using arr.sort(reverse=True) Jan 28, 2020 at 7:00