```
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL) return;
queue<pair<TreeLinkNode*, int> > q;
q.push(make_pair(root,0));
while(!q.empty()) {
TreeLinkNode* x = q.front().first;
int depth = q.front().second;
q.pop();
if (q.empty() || q.front().second != depth) {
x->next = NULL;
} else {
x->next = q.front().first;
}
if (x->left != NULL) {
q.push(make_pair(x->left,depth + 1));
}
if (x->right != NULL) {
q.push(make_pair(x->right,depth + 1));
}
}
}
};
```

The idea of this code is just broad first search and keep track on depth of each vertex. When we know the depth of a vertex we can find out where "Next" should point.

But the problem is that in statement's notes was mentioned that we could use only constant extra space.

Here I use at most O(log n) - because in binary tree each level contains at most O(log n) vertexes and in each moment I contain only at most two levels in queue. Therefore, I get O(log n) memory complexity. Couldn't find out how to rid off in my algorithm of this memory or find another approach.

Thanks for any answers.