This is acutally a BFS using the extra pointer on the parent level.

We find the start node in the next level while we connect the nodes in next level.

```
class Solution(object):
def connect(self, root):
"""
:type root: TreeLinkNode
:rtype: nothing
"""
next, pre = None, None
p = root
while p:
if p.left:
if not next:
next = p.left
if pre:
pre.next = p.left
pre = p.left
if p.right:
if not next:
next = p.right
if pre:
pre.next = p.right
pre = p.right
if not p.next:
p = next
pre = next = None
else:
p = p.next
```

An even shorter version but it's much slower.

```
next = pre = None
p = root
while p:
if p.left:
if pre:
pre.next = p.left
pre = p.left
if p.right:
if pre:
pre.next = p.right
pre = p.right
next = next or p.left or p.right
if not p.next:
p = next
pre = next = None
else:
p = p.next
```