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

Question

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.

Answer 3

This subroutine is for the insertion in the tree where tree structure is

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

{
       data = n;
       left = right = NULL;
    }
};

The algorithm is:
1. If tree is empty insert new node.
2. If data of new node is greater than data of root node make the new node
root of tree.
3. else insert new node in the left subtree of tree.

tree * insert(tree *root,int n)

{

if(root == NULL)
{

    root = new tree(n);

    return root;
}
else
{

    if(n > root -> data)
    {
        tree * t = new tree(n);

        t -> left = root;

        return t;
    }

    else


    {

        root -> left = insert(root -> left,n);

        return root;
    }
    }
}

Answer 4

The currently accepted answer gives a good on-line algorithm. A somewhat simpler solution---which is not on-line and therefor possibly cheating---is to store a sorted linked list in the parent pointers.

In other words: sort the data; put the largest item in the root, make one of its subtrees empty and recursively construct a post-order-sorted tree of the remaining n-1 items into the other subtree.

The tree will have height n, the single leaf is the head of the list and the root is the tail-most element. If you walk through the tree from leaf to root the elements will form an increasing sequence, and this path will correspond exactly to a postorder traversal.

Answer 5

Deletion

• if leaf, then delete regularly
• if it has only one son connect son to father
• else, delete the root,replace it with its right son,then connect left sub-tree to leftmost vertex in right sub-tree.

for example:

    7                                                            6
   / \                                                          / \
  3   6             =========DELETING 7 ============>          4   5
 / \ / \                                                      /    
1  2 4  5                                                    3
                                                            / \
                                                           1   2

Answer 6

First of all note that the best complexity of solving this problem is O(nlogn) otherwise it will be possible to sort array in less than O(nlogn) by creating this tree and do postorder(and it's impossible). Also, it's more useful to create a balanced tree so that the operations you might do on the tree later would be fast. Although the accepted answer is working it's O(n^2) and the tree isn't balanced.

algorithm:

1) Sort the array.

2) Create an empty balanced tree of size n.

3) Fill that tree with values from the sorted array using postorder.

complexity: O(nlogn)