# O(1) space O(n) complexity Iterative Solution

• Just share my iterative solution with O(1) space and O(n) Time complexity

``````public class Solution {

//based on level order traversal

TreeLinkNode cur = root;  //current node of current level

while (cur != null) {

while (cur != null) { //iterate on the current level
//left child
if (cur.left != null) {
if (prev != null) {
prev.next = cur.left;
} else {
}
prev = cur.left;
}
//right child
if (cur.right != null) {
if (prev != null) {
prev.next = cur.right;
} else {
}
prev = cur.right;
}
//move to next node
cur = cur.next;
}

//move to next level
prev = null;
}

}
}``````

• This post is deleted!

• +1 for a genuine O(1) space solution with elegant implementation

• This code is really elegant. Logic is great.!

• great solution. one minor thing is that I think the head and prev can be placed inside the outer while loop.

• I did some modification to increase its readability.

``````public class Solution {

TreeLinkNode prev=null;//The previous node in the lower level
TreeLinkNode curr=null;//The current node in the upper level
prev=null;
while (curr!=null){
if (curr.left!=null){
if (prev!=null)
prev.next=curr.left;
else
prev=curr.left;
}
if (curr.right!=null){
if (prev!=null)
prev.next=curr.right;
else
prev=curr.right;
}
curr=curr.next;
}
}
}
}``````

• Shouldn't we see whether head is NULL before assign new value ?

• @gaopeng Because `while (cur != null)` did the same thing.

• My solution is similar, it's basicly a level BFS without using additional qeue, as the next link already serves the queue functionality..

The difference of my solution is to introduce a dummy head node, which can save some if/else when dealling the first element in the list.

``````   public class Solution {
public static void connect(TreeLinkNode root) {
for(; n != null; n = n.next){
if(n.left != null){
tail.next = n.left;
tail = tail.next;
}

if(n.right != null){
tail.next = n.right;
tail = tail.next;
}
}
}
}
}``````

• Check out my solution :)

``````void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode * start = root;//start of cur level
TreeLinkNode * end = root;//end of all levels
TreeLinkNode * levelEnd = root;//cur level's end
while (start != NULL)
{
if (start->left != NULL)
{
end->next = start->left;
end = end->next;
}
if (start->right != NULL)
{
end->next = start->right;
end = end->next;
}
if (start == levelEnd)
{
start = start->next;//start points to next level
levelEnd->next = NULL;//set cur level's next to NULL
levelEnd = end;//set cur level's end as next level's end
}
else
{
start = start->next;
}
}
}``````

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.

• can you explain why is the time complexity O(n)? I think it's O(n*logn)

• For each node, we traverse its 2 children. So 2*n times totally, O(n) time complexity.

• After traverse one layer, how did you jump to the next layer? Could you please explain that?

• OK I know that now. nextHead.next always points to the first node of the next layer.

• ``````    public static void connect(TreeLinkNode root) {
if(root==null) return;
while(nextLevel!=null) {
nextLevel = null;
while(current!=null) {
if(current.left!=null || current.right!=null) {
if(nextLevel==null) nextLevel = (current.left!=null)?current.left:current.right;
if(current.left!=null) {
currChild.next = current.left;
currChild = currChild.next;
}
if(current.right!=null) {
currChild.next = current.right;
currChild = currChild.next;
}
}
current=current.next;
}
current=nextLevel;
}
}
``````

My solution O(1) space, O(n) time

• ``````public void connect(TreeLinkNode root) {
if (root == null)
return;
dummy.next = root;
while (dummy.next != null) {
TreeLinkNode cur = dummy.next, pre = dummy;
dummy.next = null;
while (cur != null) {
if (cur.left != null)
pre = pre.next = cur.left;
if (cur.right != null)
pre = pre.next = cur.right;
cur = cur.next;
}
}
}``````

• The idea of using a `nextHead` node is really clever!

• Wow, concise code!

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