Post-Order Traversal

What is Post-Order Traversal ?  And its implementation

Traversal

Traversal is a process to all the nodes of a tree. Generally, we traverse a tree to Search or to print all the values it Contains.

Post-order Traversal

In this method, we visit left subtree first, then we visit right subtree and finally the root node (Every node can be a subtree).
So, first we traverse the left subtree recursively. we call Post-order(left-subtree).Then we call Post-order(right-subtree) and finally we visit the root (Visiting means Printing in this context).

Algorithm

Step 1 : Recursively traverse the left-subtree till it reach the leaf. Do this by calling function Post-order(left-subtree).

Step 2 : Recursively traverse the right-subtree till it reach the leaf. Do this by calling Post-order(right-subtree).

Step 3 : Visit the root node. we will print value here.

Note : Post-order(left-subtree) calls again Post-order(left-subtree) and Post-order(right-subtree) it goes until node null.
Do this until all the nodes are traversed and printed.

Example

Figure : Binary tree

Figure : Post-order applied on binary tree

In this diagram, Algorithm starts with A then goes to the left subtree that is B, then D and it reaches F (leftmost node) prints it, then goes to the right-subtree calls post-order(right-subtree) and finally visits root and prints it.

Output : F -> G -> D -> E -> B -> H -> I -> C -> A

C++ Program

/* Code for Post-order Traversal*/
#include <stdio.h>
#include <stdlib.h>
 
/* implementation of the binary tree with pointers to left child node and right child node*/
struct node
{
     char data;
     struct node* left;
     struct node* right;
};
/*In this function we are creating a node with the given data and null left and right pointers  */ 
struct node* CreateNewNode(char data)
{
     struct node* node = (struct node*)
                                  malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;
     return(node);
}
/*This is the recursive function for Postorder traversal*/
void PostorderTraversal(struct node* node)
{
     if (node == NULL)
          return;
     PostorderTraversal(node->left);/*Recrsion on Left sub-tree*/
     PostorderTraversal(node->right); /*Recursion on Right sub-tree*/
     printf("%c ", node->data); /*printing data of the node*/
     
}
     
/*main fuction to test the code*/
int main()
{
     /*Here we are creating a tree by inserting elements*/
     /*This is the implementation of tree given in the above example*/
     struct node *root  = CreateNewNode('A');
     root->left             = CreateNewNode('B');
     root->right           = CreateNewNode('C');
     root->right->left     = CreateNewNode('H');
     root->right->right      = CreateNewNode('I');
     root->left->left     = CreateNewNode('D');
     root->left->left->left     = CreateNewNode('F');
     root->left->left->right     = CreateNewNode('G');
     root->left->right   = CreateNewNode('E'); 
     
     printf("Post-order traversal of the given input binary tree is : \n" );
     PostorderTraversal(root);  
     return 0;
}
Try It
 
Time complexity : O(n)

Let Complexity function be : C(n)

Number of nodes one side of the root be m So,
C(n) = C(m) + C(n-m-1)

Case 1

If m = 0,
C(n) = C(0) + C(n-1) + c
We know, C(n-1) = C(0) + C(n-2) + c
Therefore,
C(n) = 2C(0) + C(n-2) + 2c
C(n) = 3C(0) + C(n-3) + 3c
C(n) =  4C(0) + C(n-4) + 4c
….…………………………………
C(n) = nC(0) + nc
C(n) = n(c + C(0))
C(0) will be some constant p
C(n) = n(c + p)
C(n) =Θ(n)

Case 2

If left and right have equal number of nodes, then
C(n) = 2C(n/2) + c
By using master theorem,
We get C(n) = Θ(n)

Therefore, Time complexity = O(n)

Space Complexity
O(h)
h = Height of the tree


Next > < Prev
Scroll to Top