/**

- Definition for binary tree with next pointer.
- struct TreeLinkNode {
- int val;
- TreeLinkNode *left, *right, *next;
- TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
- };

*/

class Solution {

public:

void connect(TreeLinkNode *root) {

if (root == NULL)

return;

queue<TreeLinkNode *> q;

TreeLinkNode *temp = NULL;

int t = 1;

q.push(root);

TreeLinkNode *p;

while (!q.empty()){

for (int i = 1; i <= t; i++){

p = q.front();

q.pop();

if (p->left)

q.push(p->left);

if (p->right)

q.push(p->right);

if (i == 1){

temp = p;

}

else{

temp->next = p;

temp = p;

}

}

t << 1;

}

}

};