Tree, Linked list creation problem

Imagine you have an unbalanced binary search tree. Now make a linked list of all the nodes at every depth(level) of the tree. Assume every node along with a left and a right pointer also has a next pointer. To make the linked list inside the binary tree for every level, the next pointer of the first node at every depth should point to the next node at the same depth in the tree and so on for the other nodes. What is the complexity of your algorithm.

            10
         /      \
        5         20
      /    \    /
     3     6   15

         ~~~~ TO ~~~~
            10
         /      \
        5 ----> 20
      /    \    /
     3---> 6-->15

Answer:

Here is a solution of time and spacecomplexity O(n)
Here we do a breadth first search using a queue, and maintain the previous
node and its depth to create the linked list.

struct Node
{
    int val;
    Node *next;
    Node *left;
    Node *right;
};

void LinkifyTree(Node* root)
{
    Queue q;
    // contains the node and the depth at which the node occurs.
    typedef pair NodeInfo;
    // the previous node and its depth.
    Node *prev_node = NULL;
    int prev_depth = -1;

    q.enqueue(make_pair(root,0));
    while( !q.isempty())
    {
        NodeInfo ni = q.dequeue();
        if (prev_node && (prev_depth == ni.second) )
        {
            /* previous node exists and the depth of the previous
             * node is equal to the current node
             * */
            prev_node->next = ni.first;
        }
        else
        {
            ni.first->next = NULL;
        }
        prev_node = ni.first;
        prev_depth = ni.second;

        /* add the child nodes along with the depth */
        q.enqueue( make_pair(ni.first->left, ni.second+1) );
        q.enqueue( make_pair(ni.first->right, ni.second+1) );
    }
}