- convert BST into array using inorder traversal. This will give me an array in increasing order and can be completed in O(n)
- create a binary search tree by selecting the middle element in array in O(1), put it as a root, and recursively do the same for a right part of an array (putting the value as a root for a right subtree) and the same for the left part. This will also run in O(n)
So in my opinion I can achive absolutely the same in O(n). What is the advantage of DSW algorithm in comparison to this one?
Asked By : Salvador Dali
Answered By : Raphael
The algorithm […] is in-place.
You algorithm requires at least twice as much space. This is a significant drawback on huge data sets. A further possible advantage (I did not check) lies in the constant factors of the runtime function. Intuitively, you always construct a perfectly balanced BST so you may well do (lots) more work than DSW, even if you are still linear. Again, even a factor of magnitude $< 10$ is significant on huge data sets. In my opinion, this question is more interesting: why use simple BST + DSW instead of using balanced BSTs in the first place? (The answer is hinted at in the article, too.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37995
