def bfs_queue(root):
   q = collections.deque(root)
   while q:
       node = q.popleft()
       print node.val
       if node.left:
          q.append(node.left)
       if node.right:
          q.append(node.right)

def bfs_no_queue(root):
   q = [root]
   while q:
       new_q = []
       for node in q:
          print node.val
          if node.left:
             new_q.append(node.left)
          if node.right:
             new_q.append(node.right)
       q=new_q