If the pre-order traversal of a binary search tree is 6, 2, 1, 4, 3, 7, 10, 9, 11, how to get the post-order traversal?
You are given the pre-order traversal of the tree, which is constructed by doing: output, traverse left, traverse right.
As the post-order traversal comes from a BST, you can deduce the in-order traversal (traverse left, output, traverse right) from the post-order traversal by sorting the numbers. In your example, the in-order traversal is 1, 2, 3, 4, 6, 7, 9, 10, 11.
From two traversals we can then construct the original tree. Let's use a simpler example for this:
The pre-order traversal gives us the root of the tree as 2. The in-order traversal tells us 1 falls into the left sub-tree and 3, 4 falls into the right sub-tree. The structure of the left sub-tree is trivial as it contains a single element. The right sub-tree's pre-order traversal is deduced by taking the order of the elements in this sub-tree from the original pre-order traversal: 4, 3. From this we know the root of the right sub-tree is 4 and from the in-order traversal (3, 4) we know that 3 falls into the left sub-tree. Our final tree looks like this:
2
/ \
1 4
/
3
With the tree structure, we can get the post-order traversal by walking the tree: traverse left, traverse right, output. For this example, the post-order traversal is 1, 3, 4, 2.
To generalise the algorithm:
Using the above algorithm, the post-order traversal associated with the pre-order traversal in the question is: 1, 3, 4, 2, 9, 11, 10, 7, 6. Getting there is left as an exercise.