"""Added the height() function as an exercise for act 27"""
from pylistqueue import Queue

class BinTree:
  """Generic binary tree"""
  
  def __init__( self, root = None ):
    """Constructor to define a root"""
    self.root = root

  def height( self ):
    """Recursively compute the height of a binary tree"""
    return self._height_rec( self.root )

  def _height_rec( self, node ):
    """Helper function to compute height"""
    if node is None:
        return -1
    else:
        return 1 + max(self._height_rec(node.left), \
                       self._height_rec(node.right))

  def count( self ):
    """Count how many nodes"""
    return self.count_nodes_1( self.root, 0 )

  def count_nodes_1(self, R, count = 0):
    if R is None:
        return count

    return self.count_nodes_1(R.left, self.count_nodes_1(R.right, count + 1))

  def count_nodes( self, node ):
    """Helper function to count nodes"""
    if node is None:
      return 0
    else:
      return 1 + self.count_nodes( node.left ) + \
        self.count_nodes( node.right )

  def inorder( self ):
    """Wrapper function for 'inorder'"""
    self.inorder_trav( self.root )
    print()

  def preorder( self ):
    """Wrapper function for 'preorder'"""
    self.preorder_trav( self.root )
    print()

  def postorder( self ):
    """Wrapper function for 'postorder'"""
    self.postorder_trav( self.root )
    print()

  def levelorder( self ):
    """Wrapper function for 'levelorder'"""
    self.breadth_first_trav( self.root )
    print()

  def inorder_trav( self, subtree ):
    """Traverse the tree inorder"""
    if subtree is not None :
      self.inorder_trav( subtree.left )
      print( subtree.data, end = ', ' )
      self.inorder_trav( subtree.right )
    
  def postorder_trav( self, subtree ):
    """Traverse the tree postorder"""
    if subtree is not None :
      self.postorder_trav( subtree.left )
      self.postorder_trav( subtree.right )   
      print( subtree.data, end = ', ' )    
    
  def preorder_trav( self, subtree ):
    """Traverse the tree postorder"""
    if subtree is not None :
      print( subtree.data, end = ', ' )
      self.preorder_trav( subtree.left )
      self.preorder_trav( subtree.right )   

  def breadth_first_trav( self, bintree ):
    """Traverse the binary tree in breadth-first (level) order"""
    # Create a queue and add the root node to it.
    q = Queue()
    q.enqueue( bintree )
  
    # Visit each node in the tree.
    while not q.is_empty() :    
      # Remove the next node from the queue and visit it.
      node = q.dequeue()
      print( node.data, end = ', ' )
    
      # Add the two children to the queue.
      if node.left is not None :
        q.enqueue( node.left )
      if node.right is not None :
        q.enqueue( node.right )