Filling an empty binary tree as a binary search tree without changing the structure (Node binding)

Question

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

The method I came across was to sort the array and then move its element one after the other, putting each data element in the first empty node file in the tree. But I guess this is not true since I was not selected.

Sorry if algorithm issues are not resolved. I will take this if there is such a problem ...

Answer 1

Not only your decision is correct, but also better (in the asymptotic sense), assuming that only comparisons < or > are allowed between data elements.

Your solution involves sorting the data, which takes O (n log n) time and then inserts it into the tree in a roundabout way, which takes O (n) time for the total O (n log n) time complexity. Please note that after constructing the binary search tree, we can read all of its data in a sorted order using traversal in the order - that is, the solution to the interviewer's problem can be used to sort any given sequence of data elements.

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

Note that this binding is not performed if we assume that the input values ​​are small integers limited by some constant, since then operations such as radix sorting can sort in O (n) time.

Answer 2

That's right, when you sort an array and pass it to an immutable inorder tree, then the tree fills correctly. But maybe there is a better way to solve this problem ... without sorting, or maybe the other question was wrong ... Sorry