BST to linked list by depth

/* From Cracking the Coding Interview 4-4.

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i e , if you have a tree with depth D, you’ll have D linked lists)*/

/* The implementation provided in the book works well. It uses O(n) space where n is the number of nodes in the binary search tree.

However, if we are allowed to modify the node struct, we can do it in place. In the new node struct, besides the left and right pointers, we also add a next pointer. Using BFS, we link nodes in each level together and store the head node in a vector. The time complexity is still O(n) and space is O(1). Thanks to Little P for suggesting this solution. 

*/

struct node{

    node(int v = 0);

    node * left;

    node * right;

    node * next;

    int value;

};

node::node(int v): value(v), left(nullptr), right(nullptr), next(nullptr) { }

vector<node *> bst2list(node * root) {

    vector<node *> v;

    queue<node *> q;

    unsigned depth = 0;

    q.push(root);

    while (!q.empty()) {

        node * head = new node();

        v.push_back(head);

        size_t size = q.size();

        node * levelHead = v[depth];

        while (size--) {

             node * n = q.front(); q.pop();

            levelHead->next = new node(n->value);

            levelHead = levelHead->next;

             if (n->left) {

                q.push(n->left);

             }

             if (n->right) {

                q.push(n->right);

            }

        }

        ++depth;

    }

    for (unsigned u = 0; u < v.size(); ++u) {

        node * n = v[u];

        v[u] = v[u]->next;

        delete n;

    }

    return v;

}