# UVa 10701

## Summary

Given the pre-order and in-order traversals of a binary tree which nodes are alphabets [a-zA-Z].

Print its post-oder traversal.

## Explanation

Let :

``` N be the number of nodes
pre[] be the array of the pre-order traversal
in[] be the array of the in-order traversal
position[x] be the position of the alphabet x in the in[] array
```

Note: all array index starts from 0

Now you can print the post-order traversal using this recursive method:

``` post(start, end){
if (start > end) return
ch = pre[idx++]
post(start, position[ch]-1)
post(position[ch]+1, end)
print ch
}
```
``` idx = 0
post(0, N-1) // this will print the tree in post-order traversal
```

The idea of the recursive post method is that it directly traverse the tree using post-order-traversal-manner, characterized by printing the alphabet ch after traversing to the left and right of the nodes. Variables start and end represent the range for the current node. Traversing to the left child of the current node is done by calling post(start, position[ch]-1), this updates the ranges for the left child. It works the same for the right child. FYI, these ranges are taken from the position of the alphabet from the in-order array in[].

The in-order array gives the information of the child nodes. It tell which nodes resides on the left of the current node and which nodes resides on the right.

The pre-order array gives the information of the next node to be visited.

Combining these two information, we can solve the problem. --Felix halim 00:42, 26 Nov 2005 (EST)