UVa 10701

From Algorithmist
Jump to navigation Jump to search

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 :

 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)


Implementations[edit]