Populate Next Right Pointers Tree

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.

Given the following 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

Method:

Use the next pointer to traverse current level, keep track of a previous node in next level and also keep track of the start of next level. (If prev is null, then set the start)

Solution:

Time: O(n)
Space: O(1)

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode levelStart = root;
        while (levelStart != null) {
            TreeLinkNode curr = levelStart;
            TreeLinkNode prev = null;
            // set next level start to null, otherwise never end
            levelStart = null;
            while (curr != null) {
                for (TreeLinkNode child : Arrays.asList(curr.left, curr.right)) {
                    if (child != null) {
                        // this child will be the first node of next level
                        if (prev == null) {
                            levelStart = child;
                        } else {
                            prev.next = child;
                        }
                        prev = child;
                    }
                }
                curr = curr.next;
            }
        }
    }
}