Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 566
bragboy Avatar asked Feb 07 '10 13:02

bragboy


People also ask

What is the post-order traversal of following binary tree?

Post-order Traversal In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

Is it possible to construct a binary tree uniquely whose pre order and post-order traversals are given?

It is not possible to construct a general Binary Tree from preorder and postorder traversals (See this). But if know that the Binary Tree is Full, we can construct the tree without ambiguity.


1 Answers

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.

like image 160
sepp2k Avatar answered Nov 15 '22 22:11

sepp2k