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)
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). \$\endgroup\$ – greybeard Jan 28 '20 at 11:29