Only after I finished the solution I realized that the problem requires only O(1) space. The following solution uses O(depth) space to store the current right node of each level and uses "reversed pre-order" traversal (i.e., parent->right child->left child) for recursion.

```
class Solution {
public:
vector<TreeLinkNode*> rightNodes; // rightNodes[i]: the current right node at level i
void connect(TreeLinkNode *r) {
connectAtLevel(r);
}
void connectAtLevel(TreeLinkNode *r, int level = 0) {
if (!r) return;
if (rightNodes.size() == level) { // node "r" is the rightmost node of this level
r->next = NULL;
rightNodes.push_back(r);
}
else { // use previously stored right node as the ->next of the current node at this level
r->next = rightNodes[level];
rightNodes[level] = r;
}
connectAtLevel(r->right, level+1);
connectAtLevel(r->left, level+1);
}
};
```