DSW Algorithm (in-place linear time BST balancing)

dsw.h

#include <memory>

template<class T>
struct node {
    T val;
    node *left;
    node *right;

    node() : left(nullptr), right(nullptr) {}
    node(T v) : val(v), left(nullptr), right(nullptr) {}
};

template<class T>
void tree_to_vine(node<T> *root, int& size)
{
     auto vine_tail = root;
     auto remainder = vine_tail->right;
     size = 0;
     while (remainder) {
         if (!remainder->left) {
             vine_tail = remainder;
             remainder = remainder->right;
             ++size;
         }
         else { // (right?) rotation at remainder
             auto tempptr = remainder->left;
             remainder->left = tempptr->right;
             tempptr->right = remainder;
             remainder = tempptr;
             vine_tail->right = remainder;
         }
     }
}

template<class T>
void compression(node<T> *root, int count)
{
    auto scanner = root;
    while (count--) {
        auto child = scanner->right;
        scanner->right = child->right;
        scanner = scanner->right;
        child->right = scanner->left;
        scanner->left = child;
    }
}

template<class T>
void vine_to_tree(node<T> *root, int size)
{
    auto leaf_count = size - ((1<<(31 - __builtin_clz(size+1))) - 1);
    compression(root, leaf_count);
    size -= leaf_count;
    while (size > 1) {
        compression(root, size >>= 1);
    }
}

template<class T>
void rebalance(node<T>*& root)
{
    auto pseudo_root = std::make_unique<node<T>>();
    auto size = 0;
    pseudo_root->right = root;
    tree_to_vine(pseudo_root.get(), size);
    vine_to_tree(pseudo_root.get(), size);
    root = pseudo_root->right;
}

main.cpp

#include "dsw.h"

#include <iostream>
#include <queue>

int main()
{
    auto one = std::make_unique<node<int>>(1);
    auto two = std::make_unique<node<int>>(2);
    auto thr = std::make_unique<node<int>>(3);
    auto fur = std::make_unique<node<int>>(4);
    auto fiv = std::make_unique<node<int>>(5);
    auto six = std::make_unique<node<int>>(6);
    auto sev = std::make_unique<node<int>>(7);
    auto egt = std::make_unique<node<int>>(8);

    /**      4
     *      / \
     *     /   \
     *    3     8
     *   /     /
     *  1     7
     *   \   /
     *    2 5
     *       \
     *        6
     */

    one->right = two.get();
    thr->left  = one.get();
    fur->left  = thr.get();
    fur->right = egt.get();
    egt->left  = sev.get();
    sev->left  = fiv.get();
    fiv->right = six.get();

    auto root = fur.get();
    rebalance(root);

    std::queue<decltype(root)> q;
    q.push(root);
    auto depth = 0;
    while (!q.empty()) {
        auto s = q.size();
        std::cout << "Depth [" << depth++ << "]: ";
        while (s--) {
            auto x = q.front();
            q.pop();
            std::cout << x->val << " ";
            if (x->left)  q.push(x->left);
            if (x->right) q.push(x->right);
        }
        std::cout << std::endl;
    }
}