Java Solution with Constant Space Complexity!


#1

The Editorial and Lightweight solutions for java uses lists and recursion respectively, even though question specifies not to do so. Here is my constant space solution:

public class Solution {
/*
*   Here operations are performed on one level lower.
*   Refer solution approach for better explanation.
*/
public void connect(TreeLinkNode root) {
    for (TreeLinkNode currentLevel = root; currentLevel != null;) {
        TreeLinkNode i = currentLevel, next = i;
        for (; i != null; i = next) {
            next = findNextNodeWithChildren(next.next);

            TreeLinkNode child = null;
            if (next != null)
                child = (next.left != null ? next.left : next.right);

            if (i.left != null)
                i.left.next = (i.right != null ? i.right : child);
            if (i.right != null)
                i.right.next = child;
        }

        if (currentLevel != null && currentLevel.left != null)
            currentLevel = findNextNodeWithChildren(currentLevel.left);
        else if (currentLevel != null)
            currentLevel = findNextNodeWithChildren(currentLevel.right);
    }
}

private TreeLinkNode findNextNodeWithChildren(TreeLinkNode a) {
    for (; a != null; a = a.next) {
        if (a.left != null || a.right != null)
            return a;
    }
    return null;
}
}