# O(1) space solution

• ``````public class Solution {
if (root == null) return; // simple
if (root.left == null && root.right == null) return; // simple
TreeLinkNode last = root.right; if (last == null) last = root.left;
// last means the rightest of the existing sons.
// first means the leftest of the sons of right brothers of the root.
while (true) {
if (first == null) break;
//as far as somne of our right brothers has children we shoudl link our last with it.
if (first.left != null) {
last.next = first.left;
break;
}
if (first.right != null) {
last.next = first.right;
break;
}
first = first.next;
}
// linking our childrens if both exists
if (root.left != null && root.right != null) {
root.left.next = root.right;
}

connect(root.right);
connect(root.left);
}``````

• Not O(1) space complexity. The recursive call uses additional memory proportional to the height of the tree.

• if it's recursive, it's never space O(1)

• ``````public class Solution {

while(start!=null){
if(start.left==null && start.right==null){ // start node indicates the first non-leaf node of current level being processing.
start=start.next;
continue;
}
p=start; // Begin from start node, node p and node q finish the connect task of next level.
while(p!=null){
q=p.next;  /* node q is the next non-leaf node right after p*/
while(q!=null && q.left==null && q.right==null){
q=q.next;
}
if(q==null){ // this means no other non-leaf node left, just finish connect node p's children
if(p.left!=null && p.right!=null)
p.left.next=p.right;
}
else{
if(p.left!=null && p.right!=null){
p.left.next=p.right;
p.right.next=(q.left!=null)?q.left:q.right;
}
else if(p.left==null && p.right!=null){
p.right.next=(q.left!=null)?q.left:q.right;
}
else{
p.left.next=(q.left!=null)?q.left:q.right;
}
}
p=q;
}
start=(start.left!=null)?start.left:start.right; // start node goes to first non-leaf node of next level and repeat the above process
}
}
``````

}

• This is O(1) space solution

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