Python 3 solution using BFS


#1
class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        q = []
        if not root:
            return root
        else:
            q.append([0,root])
            
        while(q):
            dep,x = q.pop(0)
            if not q:
                return root
            else:
                if dep == q[0][0]:
                    x.next = q[1]
            if x.left:
                q.append([dep+1,x.left])
            if x.right:
                q.append([dep+1, x.right])
                
        return root