Postorder Tree Traversal In Binary Tree In C++

Postorder Tree Traversal

Postorder traversal is a depth first algorithm. There are three types of traversals in tree: Preorder, Inorder, Postorder. In this article, postorder tree traversal is performed using recursion.

C++ Program To Find Postorder Traversal of Tree

More About Postorder Traversal:

  1. In postorder traversal, we first move to the left subtree then to the right subtree and finally print the node.
  2. Used when we want to free the nodes of the tree.
  3. It is also used to find the postfix expression.
example for postorder traversal in a binary tree

Steps To Find Postorder Traversal:

  1. Traverse the left subtree. Print the leftmost node ie 5.
  2. Move back, traverse the right subtree.
  3. Since there is no right subtree, 8 is printed.
  4. 13 is printed and the parent node is printed which is 12.
  5. Finally move, to the right subtree.
  6. 18 and 54 are printed.
  7. Print the root.

 

Stack orientation of postorder traversal in C++

Algorithm To Find Postorder Traversal:

  1. If root is NULL, return.
  2. Visit the left subtree.
  3. Visit the right subtree.
  4. Print the node.

Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
    public:
        int data;
        Treeleft = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void postorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    postorder_traversal(root -> left);
    // Visit right subtree
    postorder_traversal(root -> right);
    // Print the data
    cout << root -> data << ” “;
}
int main() {
    Tree *root = new Tree(15);
    root -> left = new Tree(12);
    root -> right = new Tree(54);
    root -> left -> left = new Tree(8);
    root -> left -> right = new Tree(13);
    root -> left -> left -> left = new Tree(5);
    root -> right -> left = new Tree(18);
    postorder_traversal(root);
    return 0;
}

 

Output:

5 8 13 12 18 54 15 

Time Complexity To Find Preorder Traversal in Binary Tree

Time Complexity

O(n)

Space Complexity

O(h)