Binary Search Tree

A binary search tree is a binary tree that satisfies all three of the following conditions.

• Every key in a node's left subtree is smaller than that node's key.
• Every key in a node's right subtree is greater than that node's key.
• The left and right subtrees are themselves binary search trees.

A preorder traversal (root → left → right) visits the root first, then the left subtree and the right subtree in order, printing each node's key. A postorder traversal (left → right → root) visits the left subtree and the right subtree first, and prints the root's key last.

Given the preorder traversal of a binary search tree, write a program that produces the postorder traversal of the same tree.

The preorder traversal of the tree is given, one key per line. Each key is a positive integer smaller than $10^6$, and there are at most 10,000 nodes. No two nodes share the same key.

Print the postorder traversal of the given binary search tree, one key per line.