While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in
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
- 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?