While reading about DayStoutWarren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time.In my opinion I can achieve absolutely the same with these simple steps: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?
What is the advantage of Day-Stout-Warren algorithm for balancing BST?
algorithms;data structures;optimization;binary trees;search trees
The Wikipedia article states: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.)