Reconstructing a binary tree from infix and prefix expressions [python]
Question: Ive been spending hours on trying to figure out how to do this, I know the
function "buildtree" has to be called recursively to draw but I just cant
figure it out, I just need a spoon-fed answer which I can then study, I have
tried to do this for so long its just not within my capabilities cause I cant
understand the logical flow of things. (Sad thing is I know this will only
take a few lines of code)

    
    
    from ListBinaryTree import ListBinaryTree
    
    def buildtree(left_inorder, left_preorder, right_inorder, right_preorder, root, tree):
        #dont know what to do.
    
    
    def main(): 
        print("Binary Tree reconstructed by glee598:") 
        inorder_seq = input("Please enter the inorder sequence: ")
        preorder_seq = input("Please enter the preorder sequence: ")
        root = preorder_seq[0]
        root_inorder_index = inorder_seq.find(root)
    
        left_inorder = inorder_seq[:root_inorder_index]
        right_inorder = inorder_seq[root_inorder_index+1:]
    
        left_preorder = preorder_seq[1:preorder_seq.find(left_inorder[0])+1]
        right_preorder = preorder_seq[preorder_seq.find(left_inorder[0])+1:]
    
        tree = ListBinaryTree(root)
    
        buildtree(left_inorder, left_preorder, right_inorder, right_preorder, root, tree)
    main()
    

The ListBinaryTree class:

    
    
    class ListBinaryTree:
            """A binary tree class with nodes as lists."""
            DATA = 0    # just some constants for readability
            LEFT = 1
            RIGHT = 2   
    
        def __init__(self, root_value, left=None, right=None):
            """Create a binary tree with a given root value
            left, right the left, right subtrees        
            """ 
            self.node = [root_value, left, right]
    
        def create_tree(self, a_list):
            return ListBinaryTree(a_list[0], a_list[1], a_list[2])
    
        def insert_value_left(self, value):
            """Inserts value to the left of this node.
            Pushes any existing left subtree down as the left child of the new node.
            """
            self.node[self.LEFT] = ListBinaryTree(value, self.node[self.LEFT], None)
    
        def insert_value_right(self, value):
            """Inserts value to the right of this node.
            Pushes any existing left subtree down as the left child of the new node.
            """      
            self.node[self.RIGHT] = ListBinaryTree(value, None, self.node[self.RIGHT])
    
        def insert_tree_left(self, tree):
            """Inserts new left subtree of current node"""
            self.node[self.LEFT] = tree
    
        def insert_tree_right(self, tree):
            """Inserts new left subtree of current node"""
            self.node[self.RIGHT] = tree
    
        def set_value(self, new_value):
            """Sets the value of the node."""
            self.node[self.DATA] = new_value
    
        def get_value(self):
            """Gets the value of the node."""
            return self.node[self.DATA]
    
        def get_left_subtree(self):
            """Gets the left subtree of the node."""
            return self.node[self.LEFT]
    
        def get_right_subtree(self):
            """Gets the right subtree of the node."""
            return self.node[self.RIGHT]
    
        def __str__(self):
            return '['+str(self.node[self.DATA])+', '+str(self.node[self.LEFT])+', '+\
     str(self.node[self.RIGHT])+']'
    

Objective: [![enter image description
here](http://i.stack.imgur.com/fpOeJ.png)](http://i.stack.imgur.com/fpOeJ.png)


Answer: I think you've just about got it, you've just put too much of your logic in
the setup code and not realized that the recursive code is going to be the
same thing.

It will be a lot easier if you change the API of your recursive `buildtree`
function to simply take the whole `inorder` and `preorder` sequences and
return a tree built out of them.

    
    
    def buildtree(inorder, preorder):
        root_val = preorder[0]
        left_size = inorder.index(root_val) # size of the left subtree
    
        if left_size > 0:
            left = buildtree(inorder[:left_size], preorder[1:left_size+1])
        else:
            left = None
    
        if (left_size + 1) < len(inorder):
            right = buildtree(inorder[left_size+1:], preorder[left_size+1:])
        else:
            right = None
    
        return ListBinaryTree(root_val, left, right)
    

