Postorder Traversal of a Binary Tree using Recursion in C++

This is a C++ Program to perform PostOrder Traversal of a given Binary Tree recursively.

Problem Description

We will be given a Binary Tree and we have to create a recursive C++ program to print all the nodes in a tree using PostOrder traversal. We have to create a separate recursive function which will traverse the tree using classes and objects.

Expected Input and Output

Case 1. Balanced Tree: When the weight on both the sides of root node is equal.

                    25
                  /    \
                 19     29
                / \     / \
              17  20   27 55

Output: 17 20 19 27 55 29 25

Case 2. Right Skewed Tree: When the internal nodes in a tree have just a right child.

Output: 5 4 3 2 1

Case 3. Tree having just one node

Note: Join free Sanfoundry classes at Telegram or Youtube

Output: 15

Problem Solution

In PostOrder Traversal of a Binary Tree, we first traverse the left subtree, then the right subtree and finally we print the value of the node. We will write a recursive function which traverses the tree as mentioned above.

Program/Source Code

Here is source code of the C++ Program for PostOrder traversal of a Binary Tree. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

/* PostOrder Traversal of a given Tree in C++ */

```
#include<iostream>
```
```
using namespace std;
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
class Tree
```
```
{
```
```
    public:
```
```
        struct node *root;
```

        struct node *createnode(int key);

        void PostOrder(struct node *root);

```
        Tree()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```

/* Function to create nodes dynamically */

struct node* Tree :: createnode(int key)

```
{
```
```
    struct node *newnode = new node;
```
```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
/* PostOrder Traversal of a Tree */
```

void Tree :: PostOrder(struct node *root)

```
{
```
```
     if(root != NULL)
```
```
     {
```
```
          PostOrder(root->left);
```
```
          PostOrder(root->right);
```
```
          cout<<root->info<<" ";
```
```
     }
```
```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    Tree t;
```

    struct node *newnode = t.createnode(25);

```
    newnode->left = t.createnode(27);
```
```
    newnode->right = t.createnode(19);
```

    newnode->left->left = t.createnode(17);

    newnode->left->right = t.createnode(91);

    newnode->right->left = t.createnode(13);

    newnode->right->right = t.createnode(55);

```
 
```
```
    /* 
```
```
     * Sample Tree 1- Balanced Tree
```
```
     *
```
```
     *              25
```
```
     *            /    \
```
```
     *          27       19
```
```
     *         /  \     /  \
```
```
     *        17  91   13  55
```
```
     */
```

    cout<<"Post Order Traversal of  tree 1 is \n";

```
    t.PostOrder(newnode);
```
```
 
```
```
    /* Creating second tree */
```

    struct node *node = t.createnode(1);

```
    node->right = t.createnode(2);
```

    node->right->right = t.createnode(3);

    node->right->right->right = t.createnode(4);

    node->right->right->right->right = t.createnode(5);

```
 
```
```
    /* Sample Tree 2-  Unbalanced Tree
```
```
     *                1
```
```
     *                 \
```
```
     *                  2
```
```
     *                   \
```
```
     *                    3
```
```
     *                     \
```
```
     *                      4
```
```
     *                       \
```
```
     *                        5
```
```
     */
```

    cout<<"\n\nPost Order Traversal  of tree 2 is\n" ;

```
    t.PostOrder(node);
```
```
 
```

    /* Creating Tree 3 having just a single node */

    struct node *root = t.createnode(15);

```
 
```

    /* Sample Tree 3- Tree having just one root node.

```
     *              15              
```
```
     */
```

    cout<<"\n\nPost Order traversal of tree 3 is\n";

```
    t.PostOrder(root);
```
```
    return 0;
```
```
}
```

Program Explanation

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the PostOrder function.
3. Traverse the right subtree by recursively calling the PostOrder function.
4. Print the info part of the current node.

Runtime Test Cases

Post Order Traversal of  tree 1 is
17 91 27 13 55 19 25
 
Post Order Traversal  of tree 2 is
13 5 4 3 2 1
 
Post Order traversal of tree 3 is
15

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - Preorder Traversal of a Binary Tree using Recursion in C++

» Next - C++ Program to Check whether Graph is Biconnected or Not

Related Posts:

Recommended Articles: