function connect(root) {
var prev_to_link = null;
var next_level_head = null;
var curr = root;
while (!!curr) {
if (!!curr.left) {
if (!!prev_to_link) {
prev_to_link.next = curr.left;
}
prev_to_link = curr.left;
if (!next_level_head) {
next_level_head = curr.left;
}
}
if (!!curr.right) {
if (!!prev_to_link) {
prev_to_link.next = curr.right;
}
prev_to_link = curr.right;
if (!next_level_head) {
next_level_head = curr.right;
}
}
if (!!curr.next) {
curr = curr.next;
}else {
curr = next_level_head;
next_level_head = null;
prev_to_link = null;
}
}
}
Javascript real O(1) solution


I just rewrite this method into Java and add some explanations. This method is very intuitive and easy to understand. Thanks for @danielwpz for this nice solution.
public class Solution { public void connect(TreeLinkNode root) { TreeLinkNode curt = root; TreeLinkNode prevNode = null; // previous node. It is used to denote "next" TreeLinkNode firstNextLevel = null; // the first node of next level of tree while (curt != null) { if (curt.left != null) { if (prevNode != null) { prevNode.next = curt.left; } prevNode = curt.left; if (firstNextLevel == null) { // firstNextLevel only need to be assigned once firstNextLevel = curt.left; } } if (curt.right != null) { if (prevNode != null) { prevNode.next = curt.right; } prevNode = curt.right; if (firstNextLevel == null) { firstNextLevel = curt.right; } } if (curt.next != null) { // when curt.next != null, go to next TreeLinkNode curt = curt.next; } else { curt = firstNextLevel; // iterate the next level firstNextLevel = null; prevNode = null; } } } }