Filling empty Binary tree as Binary search tree without changing structure (Node linkage)

Question

I had an interview today and I was asked to code this.. You have an already created unordered Binary tree with no data in any node. We have an array having equal number of elements. We have to insert data in the binary tree as a binary search tree without changing the structure of binary tree.

The method I came up with was to sort the array and then traverse its element one by one, putting each data element in the first empty inorder node in the tree. But I guess that's incorrect as I wasn't selected.

Sorry if algorithm questions aren't allowed. I'll take this down if there is an issue like this...

Answer 1

It is correct, when you sort the array and give it into the not changeable tree in inorder, then the tree is correctly filled. But maybe there is a better way to solve this task... without sorting, or maybe another question was wrong... Sorry

Answer 2

Not only is your solution correct, it's impossible to do better (in the asymptotic sense), assuming that only < or > comparisons are allowed between data items.

Your solution involves sorting the data, which takes time O(n log n), and then inserting it into the tree in an in-order traversal, which takes time O(n), for an overall time complexity of O(n log n). Notice that after building a binary search tree, we can read out all its data in sorted order using an in-order traversal -- that is, solving the interviewer's problem can be used to sort any given sequence of data elements.

Now suppose to the contrary that there is in fact some algorithm that can solve the interviewer's problem in o(n log n) time -- that is, with a strictly better time complexity than the one you gave. Then this algorithm could be used to sort the given data in strictly better than O(n log n) time. But we know that this is not possible -- O(n log n) is a lower bound on the time needed to sort n elements, if all we are allowed to do with them is compare them using < or >. Thus no such better algorithm can exist.

Note that this bound fails to hold if we assume that the input values are small integers bounded by some constant, since then operations like radix sorting can perform sorting in O(n) time.