Say you are given a list of keys K_1, K_2, K_3, ... , K_n and told that these are the keys returned, in that order, by a postorder traversal of a binary search tree.<br /><br />Can you can reconstruct the tree by reading the list left-to-right exactly once ?<br /><br />(As you go you can use the keys read so far to maintain a provisional tree. When you read the next item in the postorder traversal, you incorporate it into your provisional tree, changing/adding no more than a constant number of edges/pointers in the tree. When you have done this with the last key, you have reconstructed the tree.)<br /><br />Any help would be highly appreciated.
</div>
</div>