It is very easy to come up with a solution using recursion. But the space cost of a recursion solution is o(lgn), but not o(1). Here is my c++ solution using o(1) extra space,

```
class Solution {
public:
void connect(TreeLinkNode *root) {
if ( root == NULL ) return;
TreeLinkNode* node = root;
while (node->left) {
node->left->next = node;
node = node->left;
}
while (node != root) {
if (node == node->next->left) {
node->next->right->next = node->next;
node->next = node->next->right;
while (node->right) {
node->next->left->next = node->next;
node->right->next = node->next->left;
node = node->right;
}
node = node->next;
}
else if (node == node->next->right) {
while ( node != root && node == node->next->right) {
node = node->next;
node->right->next = NULL;
}
}
}
}
};
```