title: Reconstructing a tree using inorder and preorder traversals in Python
body: <p>I need to make a function that builds a tree from a preorder and inorder traversal, but I'm not sure where I should put the MakeNode and recursive calls to construct the tree properly.</p>
  
  <p>Assuming inorder and preorder are both a list of ints, is the following algorithm correct to reconstruct the tree using the traversals?</p>
  
  <pre><code>def build(preorder, inorder):
      root = preorder[0]
      left subtree = inorder[:root-1]
      right subtree = inorder[root+1:]
  </code></pre>
  
  <p>If so - How can one take that and construct a heap (ArrayHeap) using that algorithm recursively?
  I have a class designed to construct nodes and then I can simply use heap.add(node) to create the heap.</p>
  
  <p>Say my class to build a node is named "MakeNode" and is constructed as follows (for syntax purposes):</p>
  
  <pre><code>Class MakeNode():
      def __init__(self, character, left=None, right=None):
  </code></pre>
  
  <p>To create the root node I would need to edit the function like this:</p>
  
  <pre><code>def build(preorder, inorder, heap):
      root = preorder[0]
      node = MakeNode(root) # Creating root node here
      heap.add(node) # Adding to heap
      left subtree = inorder[:root-1]
      right subtree = inorder[root+1:]
  </code></pre>
  
  <p>But how should I use recursion to build the rest of the tree?<br>
  I can incorporate the left and right preorder for ordering purposes by doing this:</p>
  
  <pre><code>def build(preorder, inorder, heap):
      root = preorder[0]
      node = MakeNode(root)
      heap.add(node)
      left subtree = inorder[:root-1]
      # order of left subtree = preorder[1:1+left subtree]
      right subtree = inorder[root+1:]
      # order of right subtree = preorder[root+1:]
  </code></pre>
  
  <p>I don't really know how to incorporate the recursive calls to build the tree or what exactly to put for the left or right parameters when doing so.  </p>
  
  <p>If anybody has any suggestions I would appreciate them, and I'm sorry if I've been unclear.  </p>