title: Printing a binary tree hierarchy using a Depth-first iterative deepening method or Breadth-First
body: <p>I'm not a programmer, but I'm currently experimenting with binary trees in Python, and I'm wanting to create a good method for printing out the binary tree, level by level; currently I have implemented a <strong>breadth-first</strong> method, printing each level starting at the root - which works fine, but was interested in a widely accepted recursive solution.</p>
  
  <p>If I was to use a recursive method, that doesn't simply emulate the iterative breadth-first method - would I/could I use <strong>depth-first iterative deepening</strong> solution?</p>
  
  <p>I know depth-first iterative deepening is used as an efficient search method, could it be used to give me a level by level print of my tree? Or is the accepted solution here to simply keep my <strong>breadth-first</strong> method?</p>
  
  <p>Here is code to my tree class, the instantiation creates a tree structure of Fibonacci function recursion calls; I have amended this so that is saves the level into each <code>Node</code>:</p>
  
  <pre><code>from collections import deque
  
  class FibTree(object):
  """Class which builds binary tree from Fibonacci function call graph"""
  def __init__(self, n, parent, level=None):
      if level is None:
          level = 0
      self.n = n
      self.parent = parent
      self.level = level
      if n &lt; 2:
          self.left = None
          self.right = None
          self.value = n
      else:
          self.left = FibTree(n - 1, self, level + 1)
          self.right = FibTree(n - 2, self, level + 1)
          self.value = self.left.value + self.right.value
  </code></pre>
  
  <p>The Iterative Breadth-First traversal method implemented:</p>
  
  <pre><code>def level_order_breadth_first_traversal(self):
      """Level order Breadth First Traversal, returning nodes by level"""
      this_level = deque([self])  
      while this_level:
          next_level = deque()
          yield this_level
          while this_level:
              u = this_level.popleft()
              if u.left is not None:
                  next_level.extend([u.left])
              if u.right is not None:
                  next_level.extend([u.right])
          this_level = next_level
  </code></pre>
  
  <p>Could I in any way now make use of the <code>Level</code> order stored in each <code>Node</code> in my Breadth-First Traversal to Print out my Binary Tree, or do I have to do some kind of traversal regardless to the fact that I have the level order stored into the Node.</p>
  
  <p>EDIT: To show my Iteratve Deepening Depth level traversal, to attempt to print out my binary tree in level order:</p>
  
  <pre><code>def _getChildren(self,node):
      """Method to expand node"""
      hasLeft = node.left is not None
      hasRight = node.right is not None
      if hasLeft:
          yield node.left
      if hasRight:
          yield node.right
  
  def dls(self, node, depth):
      """Depth Limited Search"""
      if (depth == 0):
          return node
      elif (depth &gt; 0):
          print "(" + repr(node.i) + ")" + repr(node.value),
          children = self._getChildren(node)
          for child in children:
              self.dls(child, depth-1)
      else:
          return False
  
  def iterative_deepening(self):
      """Iterative Deepening to print out binary tree level order"""
      depth = 0
      while True:
          result = self.dls(self, depth)
          if result is not False:
              return result
          depth += 1
  </code></pre>
  
  <p>When calling the <code>iterative_deepening</code> method just returns the <code>root</code> node, instead of a list of nodes in level order.</p>
  
  <p>Thanks
  Alex</p>