Reconstructing a tree using inorder and preorder traversals in Python

Question 1

What you need to do is add the root of the pre-ordered list to the tree, and removing it from preorder list. Split the in order list as you are doing, then passing both the left and right branches recursively. Keep adding the first element of pre-order to the left of the previous node unless left_subtree is empty, then you need to add it to the right.

This is python code (already tested):

class Tree():
    def __init__(self, inorder, preorder):
        self.root = preorder[0]
        lt = inorder[:inorder.index(self.root)]
        rt = inorder[inorder.index(self.root) + 1:]
        self.build(self.root, lt, rt, preorder[1:])
    def build(self, last_node, left_subtree, right_subtree, preorder):
        left_preorder = [node for node in preorder if node in left_subtree] 
        right_preorder =  [node for node in preorder if node in right_subtree]
        if len(left_subtree) > 0:
            last_node.left = left_preorder[0]
            lt = left_subtree[:left_subtree.index(last_node.left)]
            rt = left_subtree[left_subtree.index(last_node.left) + 1:]
            self.build(last_node.left, lt, rt, left_preorder)
        if len(right_subtree) > 0:
            last_node.right = right_preorder[0]
            lt = right_subtree[:right_subtree.index(last_node.right)]
            rt = right_subtree[right_subtree.index(last_node.right) + 1:]
            self.build(last_node.right, lt, rt, right_preorder)

Question 2

From http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html, you have:

parent(i) = i/2
left(i) = 2i
right(i) = 2i+1

so you can define a class:

class ArrayHeapNode:
    def __init__(self, elements, index):
        self.elements = elements
        self.index = index

    def left(self):
        next = self.index * 2
        if next >= len(self.elements):
            return None
        return ArrayHeapNode(self.elements, next)

    def right(self):
        next = (self.index * 2) + 1
        if next >= len(self.elements):
            return None
        return ArrayHeapNode(self.elements, next)

    def value(self):
        return self.elements[self.index]

    def set_value(self, _value):
        self.elements[self.index] = _value

This gives you a class that can then function as a tree on an array representation of a binary heap according to the article. If there is no element in that branch, None is returned.

You can now create tree traversal algorithms (https://en.wikipedia.org/wiki/Tree_traversal):

def inorder_traversal(node, action):
    if not node: return
    inorder_traversal(node.left(), action)
    action(node.value())
    inorder_traversal(node.right(), action)

def preorder_traversal(node, action):
    if not node: return
    action(node.value())
    preorder_traversal(node.left(), action)
    preorder_traversal(node.right(), action)

These will also work with a traditional binary tree node:

class BinaryTreeNode:
    def __init__(self, value, left, right):
        self._value = value
        self._left = left
        self._right = right

    def left(self):
        return self._left

    def right(self):
        return self._right

    def value(self):
        return self._value

    def set_value(self, _value):
        self._value = _value

Now, you can make the traversal algorithms more flexible and python-like by doing:

def inorder(node):
    if node:
        for item in inorder(node.left()):
            yield item
        yield node.value()
        for item in inorder(node.right()):
            yield item

This allows you to write things like:

for item in inorder(tree):
    print item

You can then count the elements from the node by doing:

n = sum(1 for e in inorder(root))

This then allows you to create an empty array capable of holding n elements for the elements in the heap:

elements = [0 for x in range(n)]

or combined:

elements = [0 for x in inorder(root)]
heap = ArrayHeapNode(elements, 0)

Now, you can iterate over both trees at the same time using:

for a, b in zip(inorder(root), inorder(heap)):
    b = a

This should then assign all elements in the binary tree (root) to the correct elements in the array heap (heap) using inorder traversal. The same can be done by implementing a preorder function.

NOTE: I have not tested this code.

Question 3

def pre_order(node):
    print node #pre order ... print ourself first
    pre_order(node.left)
    pre_order(node.right)

def post_order(node):
    post_order(node.left)
    post_order(node.right)
    print node # post order print self last...

def in_order(node):
    in_order(node.left)
    print node  #in order ... between its children
    in_order(node.right)

if you have any one of these you should be able to reproduce the tree

assume we have a tree like this

    0
 1     2
3 4   5 6

our traversals would be

0,1,3,4,2,5,6 #pre order
3,1,4,0,5,2,6 #in order

so from this we know that

zero is our root
3 is our left most deepest node
6 is our right most deepest node

0 ... 3 6

our left over nodes are

 1,4,2,5 # preorder
 1,4,5,2 # in-order

from this we know that

1 is a child of zero
1 is the next level leftmost node
2 is the next level rightmost node

so we now have

      0
   1      2
 3          6

leaving us with

4,5 # pre order
4,5 # in order

from this we know that 4 is a child of 1, and therefore 5 must be a child of 2 ...

now write a function that does all that

this article may help

http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html