Alex Rivera | Logout

Pre-order to post-order traversal

Asked 2010-12-27T10:13:44.560
22

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?

Edit
Report

1 Answer

9

Pre-order = outputting the values of a binary tree in the order of the current node, then the left subtree, then the right subtree.

Post-order = outputting the values of a binary tree in the order of the left subtree, then the right subtree, the the current node.

In a binary search tree, the values of all nodes in the left subtree are less than the value of the current node; and alike for the right subtree. Hence if you know the start of a pre-order dump of a binary search tree (i.e. its root node's value), you can easily decompose the whole dump into the root node value, the values of the left subtree's nodes, and the values of the right subtree's nodes.

To output the tree in post-order, recursion and output reordering is applied. This task is left upon the reader.

answered 2010-12-27T10:28:49.740

Your Answer