While reading about Day–Stout–Warren 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?


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.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.