# Simple solution using constant space

• The idea is simple: level-order traversal.
You can see the following code:

``````public class Solution {

while(root != null){
while(root!=null){
if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
root = root.next;
}
root = tempChild.next;
}
}
}``````

• Really simple solution. But it may not using constant space. Since you create a new node at every level, the space complexity should be O(log(n)).
Any way, I think it is the simplest solution. :)
If you program in C++, you may could free the new node after the inner while loop.

• I agree with liranjiao. It is not a o(1) solution.

• not necessary to create new node every level. you can create it at the beginning and keep reusing it.

• tempChild.next = null;......instead of creating one

• Smart code.

And for each level, tempChild is just like to add a dummy head to a list.

• Actually, no need to use new, because no need to keep any information in the heap.

• A very minor modification to use only one extra temporary node, rather than creating a new temporary node every level.

``````public void connect(TreeLinkNode root) {
while (root != null) {
while (root != null) {
if (root.left != null) {
currentChild.next = root.left;
currentChild = currentChild.next;
}
if (root.right != null) {
currentChild.next = root.right;
currentChild = currentChild.next;
}
root = root.next;
}
root = tempChild.next;
tempChild.next = null;
}
}``````

• can you explain this: root = tempChild.next;

• This post is deleted!

• tempChild is dummy head of root's next level. So root = tempChild.next moves to loop next level's nodes.

• can you exlplain little more?still confused...the root=tempChild.next

• root is the head of each level. here is the one with comments

``````public void connect(TreeLinkNode root) {
//loop the head in the level
//loop the node in each level
while(node!=null){
if(node.left!=null){
child.next=node.left;
child=node.left;
}
if(node.right!=null){
child.next=node.right;
child=node.right;
}
node=node.next;
}
tmpNode.next=null;
}
}``````

• agreed with yutao.
it's ok to create a new TreeLinkNode during each loop because it lives within current loop.

• I think the explanation should be, when "TreeLinkNode currentChild = tempChild;" the currentChild is the address of the object, so every change to currentChild is the change to tempChild. So in the following two if(){}..., because of "currentChild.next = root.right;" or"currentChild.next = root.right;" the tempChild.next is change into the first node of this level. However, because of "currentChild = currentChild.next;" the currentChild change to the address of another object. So the tempChild will not change with it anymore and it will stay on the first node of this level. I think that's why tmpNode.next is the first node of each level. Am I correct

• @cx.guooutlook.com The underlying mechanics between Java and C++ are quite different. Even now, I am still confused whether Java is pass by value or reference.

• @cx.guooutlook.com

• This post is deleted!

• @gzproger i think what u said is wrong. For ex, {1,2}. tempChild->next will always point to 2, which will cause infinite loop.....

• Here's my Python version with slight modification to make O(1) space.

``````class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
while root:
curChild = sentinel
while root:
if root.left:
curChild.next = root.left
curChild = curChild.next
if root.right:
curChild.next = root.right
curChild = curChild.next
root = root.next
root = sentinel.next
sentinel.next = None
``````

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