All recursive solutions are NOT constant space solutions, as stack space is also space.

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