Python: Binary Tree Class: Reconstruct with traversals

Question

I am trying to make a function that uses my ListBinaryTree: class to constructs and prints a binary tree based on the inorder and preorder traversals given as input prompts (in string form, eg. Inorder = 213, Preorder = 123). My Binary Tree class is as follows:

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])+']'

So far I have the following:

def reconstruct():
    inorder = input("Please enter the inorder sequence:")
    preorder = input("Please enter the preorder sequence:")
    #root = preorder[0]
    #left_bottom = inorder[0]
    #right_bottom = inorder[len(inorder)-1]
    my_tree = ListBinaryTree(int(preorder[0]))
    my_tree.insert_tree_left(int(inorder[0]))
    my_tree.insert_tree_right(int(inorder[len(inorder)-1]))
    print (my_tree)

But it only works for a tree with 1 or 2 levels: An example of the output would be:

Call the function

reconstruct()

Prompt:

Please enter the inorder sequence:213
Please enter the preorder sequence:123

Print result:

[1, 2, 3]

How do I change my function so that it can construct a tree with theoretically infinite amount of traversals/ higher levels?

Prune Prune · Accepted Answer · 2015-10-21T01:25:06

First of all, the posted code does not work as you show: the class has no constructor arguments. Most of all, you need to consult your class materials to see how to reconstruct the tree from the two given orders.

The head of inorder is the root of the tree.
Find this element in the preorder.
Split the preorder at this point: elements before the root are in its left subtree; elements after are in the right subtree.
Use these to split the inorder similarly.
Recur on each of the left and right subtrees.

Does that get you going?

Let's see about that pseudo-code:

def build_tree(inorder, preorder):
    if len(inorder) == 1:
        make a one-node tree of this node
        return this tree
    head = inorder[0]
    head_pos = position of head in preorder[]
    left_pre = preorder[:head_pos]
    right_pre = preorder[head_pos+1:]
    left_in = inorder[1:-len(right_pre)]
    right_in = inorder[-len(right_pre):]
    left_tree = build_tree(left_in, left_pre)
    right_tree = build_tree(right_in, right_pre)
    make a tree that has
        head as its root
        left_tree as its left subtree
        right_tree as its right subtree
    return this tree

Python: Binary Tree Class: Reconstruct with traversals

1 Answers