# 7-line O(1) space recursive solution + O(logN) space solution (detailed explanation and picture illustration)

• This is the recursive solution inspired by @G513.
Key observation: A node `x`'s next node is:

• `x`'s right sibling if it has one;
• otherwise, `x`'s next non-leaf uncle's left-most child if it has one;
• otherwise, `NULL`.

The algorithm will first populate next pointers of `root->right` and `root->left`, then do recursion on `root->right` before `root->left` (because we need next uncle's next pointers populated before current node). Since no local variables are defined, so it should be O(1) space on recursion stack (?).

``````    void connect(TreeLinkNode *r) {
if (!r) return;
if (r->right) r->right->next = find_next(r->next);
if (r->left)  r->left->next = r->right? r->right : find_next(r->next);
connect(r->right); connect(r->left); // must do recursion on right subtree first
}
// find next non-leaf same level node's left-most child
while (r && !r->left && !r->right) r = r->next; // find next non-leaf node
return r? r->left ? r->left : r->right : NULL;  // return left-most child
}
``````

If O(logN) space is allowed instead of O(1), we could save the current next node of each level instead of looking for next non-leaf uncle's:

``````    vector<TreeLinkNode*> rightNodes;  // index is tree level
void connect(TreeLinkNode *r) { connectAtLevel(r); }
void connectAtLevel(TreeLinkNode *r, int level = 0) {
if (!r) return;
if (rightNodes.size() == level) { r->next = NULL; rightNodes.push_back(r); }
else { r->next = rightNodes[level];  rightNodes[level] = r; }
connectAtLevel(r->right, level+1); connectAtLevel(r->left, level+1);
}
``````

• @zzg_zzm Great Idea! but I doubt it it's real O(1) extra Space, I found some discussions on Google, and this may be useful for analyzing: `a recursive algorithm will require space O(depth of recursion)`, the tree depth maybe reach to Lg(n) on average case, and `connect()` may need to reach to `!r` which indicates it reaches to some leaf already.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.