# Definition for a  binary tree node

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

#         self.next = None

class Solution:

    # @param root, a tree node

    # @return nothing

    def connect(self, root):

        """

        We use a BFS from the root, so that we can traverse the tree level by level.

        We need two queues, to store the nodes of this level and next.

        """

        if root is None:

            return

        q = [root]

        while q:

            new_q = []

            for i in xrange(len(q)-1):

                q[i].next = q[i+1]

            q[-1].next = None

            for node in q:

                if node.left:

                    new_q.append(node.left)

                if node.right:

                    new_q.append(node.right)

            q = new_q