Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Construct a Tree

Tags:

How can I construct a tree given its inorder and preorder traversal? I am just looking for an efficient algorithm.

like image 490
Carlin Avatar asked Feb 02 '10 14:02

Carlin


People also ask

How do you make a tree?

Create a new tree node tNode with the data as the picked element. Find the picked element's index in Inorder. Let the index be inIndex. Call buildTree for elements before inIndex and make the built tree as a left subtree of tNode.

Is it possible to construct a binary tree from inorder?

Yes it is possible to construct a binary search tree from an inorder traversal. Observe that an inorder traversal of a binary search tree is always sorted. There are many possible outcomes, but one can be particularly interested in producing a tree that is as balanced as possible, so to make searches in it efficient.


2 Answers

A blatant copy and paste from Sun's (Oracle now, I guess...) forum:

Question:
Can anybody help me on how to construct Binary tree from inorder and postorder traversals,i just want to know the algorithm so that i can apply it.

Answer:
Let p_1, p_2 ... p_n be the postorder traversal and let i_1, i_2 ... i_n be the inorder traversal. From the postorder traversal we know that the root of the tree is p_n. Find this element in the inorder traversal, say i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n. From the inorder traversal we find all the elements in the left subtree, i.e. i_1, i_2 ... i_k-1 and in the right subtree, i.e. i_k+1 ... i_n respectively.

Remove element p_n (and element i_k == p_n). Find the rightmost element p_j in p_1, p_2 ... p_j ... p_n-1 where p_j is an element in i_1, i_2 ... i_k-1. This is the root of the left subtree of the original tree. Split p_1, p_2 ... p_j and p_j+1 ... p_n-1 and i_1, i_2 ... i_k-1 and i_k+1 ... i_n. Now you have two subsequences representing the postorder and inorder traversal of the two subtrees of the original tree.

Author: JosAH.

I've implemented the algorithm once following Jos' instructions, and it worked perfectly!

like image 151
Bart Kiers Avatar answered Nov 14 '22 22:11

Bart Kiers


Since this is homework, I won't give you a full answer, but hopefully, enough to get you moving.

Imagine you have preorder traversal of, say this tree.

The traversal gives you 2-7-2-6-5-11-5 ... etc. Notice that the 5 is actually the right child of the root.

Obviously, you can't tell that from just looking at the numbers, so either you will be told about the structure of the tree, or you need to store some additional data (ie, whether the a node is the left child or right child, for example).

Parsing the tree is simply a recursive function that takes the preorder traversal as input (think about your scope when you are passing the input). As I mentioned earlier, your preorder traversal should have some additional data attached.


Efficiency:

consider how many times each node is visited when you build this tree, but also consider the operation of reading the input. Is there a way to reorganize the input faster than you can build the tree? What structure would you have to use if you need to manipulate the data.


In Order: You will need the same idea to get you through it, so I won't cover it. I'm sure someone else will, if you are desperate for it.

like image 23
Ritwik Bose Avatar answered Nov 14 '22 21:11

Ritwik Bose