# 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;
}``````

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

Scroll to Top