# UVa 10701

## Summary[edit]

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[edit]

Let :

Nbe the number of nodespre[]be the array of the pre-order traversalin[]be the array of the in-order traversalposition[x]be the position of the alphabetxin thein[]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)