When reading on the problem BST Maintenance on hackerrank, the editorialist casually says “Build the final BST in O(N) time” but I’m not able to figure out how to do this.
Specifically, given an initially empty binary search tree(plain, no fancy stuff like splays and rotates) and N keys a_1,a_2,...,a_N in order, how can I build the final BST formed after inserting all these elements in order, in O(N) time?
Without any further structure on the keys, this is provably impossible, I think: an inorder search (O(N)) would yield all the keys in sorted order, giving an O(N) comparison sort - a contradiction.
So we need to make some usage of the fact that the keys are a permutation of {1, 2, ... , N} (and so, sortable in O(N) using e.g. a counting sort). Don’t know how to do that, yet; will have a ponder when I have time (unless someone beats me to it ;))
Edit:
Gosh, the Discussion forum for that Problem is choked with spammers talking to themselves - how sad.
4 Likes
Idk about O(n) but it’s possible in at least O(n*log(n)).
Because I saw a question in one hiring challenge where we had to insert elements in given order but we need to print final BST when N is in order of 10^5. ( Understand that BST can have linear height and we cannot balance it since we had to print tree later on)
2 Likes
Its possible in n log n. Use a segment tree which answers min queries on the discovery time. Make the node with min discovery time the root then the node with min discovery time with key > key(root) the right child and that with min discovery time with key < key(root) its left child and so on. This gives an O(n log n) implementation.
Sorry for not typesetting, i typed this from my smartphone so it was easier to not.
2 Likes
Im also wondering the same thing
Btw, I built the tree in NlogN and got AC 
thanks for the input to the discussion everyone!
1 Like