title: Recursively Creating a Binary Tree Given a String Expression in Prefix Notation in Python
body: <p><a href="https://i.stack.imgur.com/3DXNJ.png" rel="nofollow noreferrer">Representation of LinkedBinaryTree that should be outputted</a><br>
      import LinkedBinaryTree</p>
  
  <pre><code>def create_expression_tree(prefix_exp_str):
  
      def create_expression_tree_helper(prefix_exp, start_pos):
          start_pos += 1
          op = ['+', '-', '*', '/']
          elem = prefix_exp[start_pos]
          if elem == ' ':
              elem = prefix_exp[start_pos+1]
              start_pos += 1
  
          if elem not in op:
              return LinkedBinaryTree.LinkedBinaryTree.Node(int(elem))
          else:
              left = create_expression_tree_helper(prefix_exp, start_pos)
              right = create_expression_tree_helper(prefix_exp, start_pos+2)
              return LinkedBinaryTree.LinkedBinaryTree.Node(elem, left, right)
  
      tree = LinkedBinaryTree.LinkedBinaryTree(create_expression_tree_helper(prefix_exp_str, -1))
  
      return tree
  
  tree1 = create_expression_tree('* 2 + - 15 6 4')
  for i in tree1.preorder():
      print(i.data, end='')
  </code></pre>
  
  <p>I implemented my own binary tree class which is shown below. Preorder() is a generator for my LinkedBinaryTree that gives the values of the tree in prefix order. With this code, I'm outputting
  *2+-151
  but it should be outputting
  *2+-1564 if the binary expression tree has been created correctly.
  I'm aware that there is an issue with numbers greater than 1 digit, but I'm not sure how to fix it without compromising the runtime (ie. using slicing). Also I'm not sure why it is omitting some of the tokens. Any ideas? (The implementation must run in linear time and use no additional parameters in the helper function I've defined). </p>
  
  <pre><code>import ArrayQueue
  
  class LinkedBinaryTree:
  
      class Node:
          def __init__(self, data, left=None, right=None):
              self.data = data
              self.parent = None
              self.left = left
              if (self.left is not None):
                  self.left.parent = self
              self.right = right
              if (self.right is not None):
                  self.right.parent = self
  
      def __init__(self, root=None):
          self.root = root
          self.size = self.subtree_count(root)
  
      def __len__(self):
          return self.size
  
      def is_empty(self):
          return len(self) == 0
  
      def subtree_count(self, root):
          if (root is None):
              return 0
          else:
              left_count = self.subtree_count(root.left)
              right_count = self.subtree_count(root.right)
              return 1 + left_count + right_count
  
  
      def sum(self):
          return self.subtree_sum(self.root)
  
      def subtree_sum(self, root):
          if (root is None):
              return 0
          else:
              left_sum = self.subtree_sum(root.left)
              right_sum = self.subtree_sum(root.right)
              return root.data + left_sum + right_sum
  
  
      def height(self):
          return self.subtree_height(self.root)
  
      def subtree_height(self, root):
          if (root.left is None and root.right is None):
              return 0
          elif (root.left is  None):
              return 1 + self.subtree_height(root.right)
          elif (root.right is  None):
              return 1 + self.subtree_height(root.left)
          else:
              left_height = self.subtree_height(root.left)
              right_height = self.subtree_height(root.right)
              return 1 + max(left_height, right_height)
  
  
      def preorder(self):
          yield from self.subtree_preorder(self.root)
  
      def subtree_preorder(self, root):
          if(root is None):
              return
          else:
              yield root
              yield from self.subtree_preorder(root.left)
              yield from self.subtree_preorder(root.right)
  
  
      def postorder(self):
          yield from self.subtree_postorder(self.root)
  
      def subtree_postorder(self, root):
          if(root is None):
              return
          else:
              yield from self.subtree_postorder(root.left)
              yield from self.subtree_postorder(root.right)
              yield root
  
  
      def inorder(self):
          yield from self.subtree_inorder(self.root)
  
      def subtree_inorder(self, root):
          if(root is None):
              return
          else:
              yield from self.subtree_inorder(root.left)
              yield root
              yield from self.subtree_inorder(root.right)
  
  
      def breadth_first(self):
          if (self.is_empty()):
              return
          line = ArrayQueue.ArrayQueue()
          line.enqueue(self.root)
          while (line.is_empty() == False):
              curr_node = line.dequeue()
              yield curr_node
              if (curr_node.left is not None):
                  line.enqueue(curr_node.left)
              if (curr_node.right is not None):
                  line.enqueue(curr_node.right)
  
      def __iter__(self):
          for node in self.breadth_first():
              yield node.data
  </code></pre>
  
  <p>I added the code here for LinkedBinaryTree class. The ArrayQueue class that is used in the implementation of the breadth traversal method is just a basic queue using a Python list as the underlying data structure.</p>