Constructing a binary tree from its in-order and post-order traversals

Hi everyone. I'm not gonna lie to you - this is part of an assignment. However, I didn't come here to ask for code.

Quote:

---

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output

1
3
255

---

Right, my only question right now is how can I construct a binary tree from its in-order and post-order traversals?

In-order: 3 2 1 4 5 7 6
Post-order: 3 1 2 5 6 7 4

Here's what I know so far in this example: 4 is the root, because it's the last element in the post-order sequence; 3 is the leftmost element, because it's the first element in the pre-order sequence.

However, I seem to have a hard time sorting out an algorithm to build the rest of the binary tree. Can you please point me in the right direction? Thank you in advance.

Well, let's keep working at this example then: 4 is the root. So 3 2 1 are on the left (from inorder); since they appear as 3 1 2 in post order, we know that 2 is the root of this subtree; we know then that 3 is on the left and 1 is on the right (from inorder).
Simillarly: 5 7 6 are on the right (from inorder); since they appear as 5 6 7 in postorder, 7 is the root of the subtree, so 5 is on the left and 6 is on the right (from inorder).

In other words: hey recursion!

You are on the right track. Using the last entry of the post-order, you can find the root of the tree. In this case, 4. So split the in-order list into two lists on either side of 4: [3 2 1] and [5 7 6].

You now have two subtrees with a root of 4, and a post-order list of 3 1 2 5 6 7. The post-order list is in two halves (not guaranteed to be equal in size mind you). These halves are just reorderings of the in-order subtrees. Since you have [3 2 1] and [5 7 6] this would imply splitting the post-order sequence into [3 1 2] and [5 6 7].

So now the original problem is reduced to two smaller problems of the same kind. This is a recursive method.

EDIT: If the tree is full, and balanced, then you do not need the post-order sequence to reconstruct the tree. See if you can understand why that's true.

Thank you both for your help. I have successfully coded an algorithm to construct those binary trees.

The output for the second one (in-order: 7 8 11 3 5 16 12 18, post-order: 8 3 11 7 16 18 12 5) is:

Quote:

---

Value: 5
Right child: 12
Left child: 7

Value: 12
Right child: 18
Left child: 16

Value: 18
Right child: null
Left child: null

Value: 16
Right child: null
Left child: null

Value: 7
Right child: 11
Left child: null

Value: 11
Right child: 3
Left child: 8

Value: 3
Right child: null
Left child: null

Value: 8
Right child: null
Left child: null

5 is the root.

---

...which seems to be correct. The output of the first one also seems to be correct, and so is the third one's output.

Finding the solution to the assignment should be piece of cake now. Thank you once again.

i could be wrong here, as i have not read this elsewhere, but this is an observation of mine.
an in-order representation of the tree flat out tells you the comparative relationship between each element, even if the tree wasn't constructed using some comparative function (such as a "question" tree or an "animal" tree), in which case an in-order traversal still imposes an order to the elements.
Using this observation, if you know the pre-order or post-order, you know which element the root is. With either representation, if you start inserting each element in the representation, starting at the root and working towards the other end, you can use the infix representation as your comparative function to reconstruct a tree identical to the original. i.e.:

for some arbitrary tree:

pre-order representation:
A B F Q N S W G K L M Z (these are not letters, but some things to which we don't know the
order, for example, A is not necessarily less then B)

in-order representation:
F S N Q W B A K M L Z G

now, we do not know how the elements where placed in the tree, but for the purposes of reconstruction, using the in-order representation, we can assume that :

F < S < N < Q < W < B < A < K < M < L < Z < G

we also know the root is A, so starting from the root and working towards the end of the list, we began inserting using the order imposed by the in-order representation. As an example, using pre-order, we know the root is A, so insert it. The next element B, according to the in-order, is less then A, so B becomes the left child of A. you continue this until you run out of elements. This works
for post-order as well, you simply work from the end of the list to the front in this case.