Code is short and easy to understand, the merge part is just like a DFS in two trees simultaneously, the order of the four recursions matters.

Then the pain is the time complexity. It's slow but just enough to get AC.

```
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
connect(root.left);
connect(root.right);
merge(root.left,1,root.right,new int[1]);
}
public void merge(TreeLinkNode rootL, int currDepth, TreeLinkNode rootR, int[] visitedDepth){
if(rootL==null || rootR==null) return;
if(currDepth> visitedDepth[0]) {
rootL.next = rootR;
visitedDepth[0]++;
}
merge(rootL.right,currDepth+1,rootR.left,visitedDepth);
merge(rootL.right,currDepth+1,rootR.right,visitedDepth);
merge(rootL.left,currDepth+1,rootR.left,visitedDepth);
merge(rootL.left,currDepth+1,rootR.right,visitedDepth);
}
}
```

Here is iterative BFS solution with O(n) time complexity and O(1) space.

Explanation for 2nd solution: It's a BFS traversal inspired by aileengw. The curr pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move curr pointer at current level and populate the the next-link at its children level. (Here the gist is we can move curr to its next because this relationship was already populated in the previous round).

```
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode curr = root;
TreeLinkNode head = null, tail = null;
while(curr!=null) {
if(curr.left!=null) {
if(tail!=null) {
tail.next = curr.left;
tail = tail.next;
}
else {
head = curr.left;
tail = head;
}
}
if(curr.right!=null) {
if(tail!=null) {
tail.next = curr.right;
tail = tail.next;
}
else {
head = curr.right;
tail = head;
}
}
if(curr.next!=null) curr = curr.next;
else {
curr = head;
head = null;
tail = null;
}
}
}
}
```