```
/*
Time complexity: O(n), Space complexity: constant extra space
*/
public static void connect2(TreeLinkNode root){
if(root == null){
return;
}
TreeLinkNode pre = null;
TreeLinkNode current = root;
TreeLinkNode currentLevelHead = root;
TreeLinkNode nextLevelHead = null;
while(currentLevelHead != null) {
current = currentLevelHead;
while (current != null) { //linking current level nodes while constructing next level
//left child
if (current.left != null) {
if (pre != null) {
pre.next = current.left;
} else {
nextLevelHead = current.left;
}
pre = current.left;
}
//right child
if (current.right != null) {
if (pre != null) {
pre.next = current.right;
} else {
nextLevelHead = current.right;
}
pre = current.right;
}
current = current.next;
}
currentLevelHead = nextLevelHead;
pre = null;
nextLevelHead = null;
}
}
```