Reconstructing a tree using inorder and preorder traversals in Python

Question

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.

Assuming inorder and preorder are both a list of ints, is the following algorithm correct to reconstruct the tree using the traversals?

def build(preorder, inorder): root = preorder[0] left subtree = inorder[:root-1] right subtree = inorder[root+1:]

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.

Say my class to build a node is named "MakeNode" and is constructed as follows (for syntax purposes):

Class MakeNode(): def __init__(self, character, left=None, right=None):

To create the root node I would need to edit the function like this:

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:]

But how should I use recursion to build the rest of the tree?
I can incorporate the left and right preorder for ordering purposes by doing this:

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:]

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.

If anybody has any suggestions I would appreciate them, and I'm sorry if I've been unclear.

tree-traversal is about visiting nodes ... it has nothing to do with inserting them ... I have no idea what you are trying to do ... pre-order is one method of traversal, another method is inorder. neither has anything to do with constructing your tree ... as such this question really confuses me ... — Joran Beasley
– Joran Beasley, Commented Apr 24, 2014 at 0:16
@JoranBeasley You can use a preorder and inorder traversal to reconstruct the tree..which is what I am trying to do. — somebody
– somebody, Commented Apr 24, 2014 at 0:17
so then you already have a pre-order traversal? werent you just asking what to put for the pre-order traversal ? just put a list probably ... — Joran Beasley
– Joran Beasley, Commented Apr 24, 2014 at 0:19
I have the preorder and inorder traversals - they are lists of ints. I am asking how to use those to properly reconstruct the tree. — somebody
– somebody, Commented Apr 24, 2014 at 0:19

tieuminh2510 · Accepted Answer · 2020-07-07 13:43:33Z

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)

reece · Accepted Answer · 2014-04-24 01:00:01Z

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.

Are the following conditions necessary for reconstruction of the tree: 1) The tree has to be BST and not just a binary tree.
@gudge The algorithms work on any binary tree. If the tree has a left node A, value B and right node C, then pre-order outputs BAC, in-order ABC and post-order ACB. This gives the property that a sorted binary tree (Binary Search Tree) will yield the items in sorted order when using in-order traversal.

Joran Beasley · Accepted Answer · 2014-04-24 00:35:20Z

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

I am trying to take the traversals and create a new heap which essentially mimicks the initial tree that the traversals were taken from. I'm trying to essentially translate the traversals into the tree it was before.
Are you trying to create a heap or a tree? I assume that you're trying to create
@Rick A heap but I was just saying tree as a generalization.
@JoranBeasley "now write a function that does all that" is what I am trying to do in my question. I am just struggling with the coding of it.

Collectives™ on Stack Overflow

Reconstructing a tree using inorder and preorder traversals in Python

3 Answers 3

Comments

2 Comments

6 Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

6 Comments

Related