Populating Next Right Pointers in Each Node I & II

Updating a solution using Queue, O(n) complexity. Actually, this solution works for both problem...

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        Queue q = new LinkedList ();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeLinkNode curr = q.poll();
                if(!q.isEmpty() && (i < size - 1))
                    curr.next = q.peek();
                if (curr.left != null)
                    q.offer(curr.left);
                if (curr.right != null)
                    q.offer(curr.right);
            }
        }
    }
}

The first one:

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Nothing but a tree-like linked list traversal.
Set parent = root and nextLevel = parent.left. Using two loops, the outer one goes down each level and the second one assign pointers.

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = root.left;
        while (parent != null && nextLevel != null)
        {
            TreeLinkNode curr = null;
            //same level
            while (parent != null)
            {
                if (curr == null)
                    curr = parent.left;
                else
                {
                    curr.next = parent.left;
                    curr = curr.next;
                }
                curr.next = parent.right;
                curr = curr.next;
                parent = parent.next;
            }
            parent = nextLevel;
            nextLevel = parent.left;
        }
        
    }
}

The second one:

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Overall it's not hard. However, I had a problem on assigning the nextLevel at the right place.
I did it outside the inner loop at first. Consider a case like this:

  1
 /   \
7    9
     /  \
    1   7
     \     \
      8    10

If I assign the nextLevel outside the inner loop like this:

while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = (parent.left == null) ? parent.right : parent.left;
            while (parent != null)
            {

When it traverse to parent = 7, there will be no nextLevel. And thus 8 will not be assigned the next pointer.

So it should be done in this way:

while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;

The code:

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = null;
        while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;
                if (parent.left != null)
                {
                    if (curr == null)
                        curr = parent.left;
                    else
                    {
                        curr.next = parent.left;
                        curr = curr.next;
                    }
                }
                if (parent.right != null)
                {
                    if (curr == null)
                        curr = parent.right;
                    else
                    {
                        curr.next = parent.right;
                        curr = curr.next;
                    }
                }
                parent = parent.next;
            }
            parent = nextLevel;
        }
        
    }
}