Construct a Tree

Question

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

Answer 1

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!

Answer 2

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.