Construct a binary tree such that the Post-order traversal should give the sorted result

Question

Hi, I know that In-order traversal(VISIT LEFT, VISIT ROOT, VISIT RIGHT) on a binary search tree gives me a sorted result. But I need to do a Post-order traversal (VISIT LEFT, VISIT RIGHT, VISIT ROOT) on a binary tree and the result should give me sorted values.

In order to achieve that, how should I construct my binary tree?

Answer 1

Since the root is visited last, it must contain the largest item. Since the left subtree is visited before the right subtree, all items in the left subtree must be smaller than any item in the right subtree.

So to construct a tree like this you can proceed as follows: If you insert an item which is greater than the root, that item becomes the new root. If you insert an item which is smaller than the root but greater than the root of the left subtree, insert it into the right subtree. Else insert it into the left subtree.

Answer 2

You need to ensure the following at each node of the tree:

• Value at the node should be greater than all the values in the left-subtree and right-subtree.
• Values in the left sub-tree should be less than values in the right subtree.