class deque(list):

def shift(self):

r = self[0]

super(deque, self).remove(r)

return r

`class Solution:`

# @param root, a tree node

# @return nothing

def connect(self, root):

if root is not None:

q = deque([(root, 0)])

while(len(q) > 0):

p, n = q.shift()

p.next = q[0][0] if len(q) > 0 and n == q[0][1] else None

q.extend([(x, n+1) for x in [p.left, p.right] if x is not None])