title: Python implementation of Breadth-First Search on Binary Search Trees
body: <p>I am trying to write a BFS algorithm for a Binary Search Tree using Python3.</p>
  
  <p>I first initialised the class, defined an insert method, and inserted some random numbers:</p>
  
  <pre><code>class Node:
      def __init__(self, data):
          self.data = data
          self.left = None
          self.right = None
  
      def insert(self, data):
          if data &lt;= self.data:
              if self.left == None:
                  self.left = Node(data)
              else:
                  self.left.insert(data)
          else:
              if self.right == None:
                  self.right = Node(data)
              else:
                  self.right.insert(data)
  
  root = Node(1)
  root.insert(0)
  root.insert(2)
  root.insert(1.5)
  root.insert(2.4)
  root.insert(1.6)
  root.insert(2.3)
  </code></pre>
  
  <p>Then, I tried to write a recursive BFS method:</p>
  
  <pre><code>    def inLineTraversal(self, queue=[]):
          if queue == []:   # Base condition
              return
          temp = queue
          for node in temp:
              print(node.data) 
              if node.left != None:
                  queue.append(node.left)
              if node.right != None:
                  queue.append(node.right)
              queue.pop(0)
          self.inLineTraversal(queue)
  </code></pre>
  
  <p>However, this produced <code>1,2,2.4,1.5,2.3,2.3,1.6</code> as opposed to the correct result of <code>1,0,2,1.5,2.4,1.6,2.3</code>.</p>
  
  <p>I later used a while loop to perform the BFS, which correctly produced <code>1,0,2,1.5,2.4,1.6,2.3</code>:</p>
  
  <pre><code>    def inLineTraversal(self):
          queue = [self]
          while queue != []:
              s = queue.pop(0)
              print(s.data)
              if s.left != None:
                  queue.append(s.left)
              if s.right != None:
                  queue.append(s.right)
  </code></pre>
  
  <p>What was wrong with the recursive solution?</p>