Question: Construct the binary tree for the inorder and post order traversal sequence given below: -
0

Inorder “INFORMATION”

Postorder “INOFMAINOTR”

Write a function to traverse a tree in postOrder

binary search tree • 1.4k views
ADD COMMENTlink
modified 17 days ago by gravatar for Sanket Shingote Sanket Shingote ♦♦ 290 written 3.5 years ago by gravatar for Sayali Bagwe Sayali Bagwe2.5k
0

Binary tree construction:

Since, R is the last element in the post order sequence, R will be the root.

Elements to the left of R will be a part of left sub tree and the elements to the right of R will be a part of right sub tree.

Further, F is the last element of post Order sequence in the left sub tree.

Hence, F will be the root element in this case.

Elements before F i.e. I and N will be a part of left sub tree and O will be a part of right sub tree.

This process can be continued for the remaining elements to obtain the resultant binary tree.

The steps mentioned above can be represented graphically as follows:

enter image description here

enter image description here

C++ function to traverse a tree in postOrder

voidBinarySearchTree::postOrder(node *ptr)
{
if (root == NULL)
        {
    cout<<"Tree is empty."<<endl;
    return;
        }
if (ptr != NULL)
        {
    postOrder(ptr->left);
    postOrder(ptr->right);
    cout<<ptr->info<<"  ";
        }
}
ADD COMMENTlink
written 3.5 years ago by gravatar for Sayali Bagwe Sayali Bagwe2.5k
Please log in to add an answer.