Traversing Tree in Postorder Sequence Using C++

What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

What is Tree Traversal?

In computer science, tree traversal is a form of graph traversal that refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

What is Postorder Traversal?

When the root node is visited last after traversing left subtree and right subtree sequentially then it is called Postorder Traversal. It is also called LRN traversal. LRN sequentially means Left Subtree, Right Subtree, Node. For each node the LRN sequence is followed in postorder traversal.

Steps of Postorder Traversal

1. Traverse the left subtree by recursively calling the post-order function. (8th line on code)
2. Traverse the right subtree by recursively calling the post-order function. (9th line on code)
3. Access the data part of the current node. (10th line on code)

Uses of Postorder Traversal

Traverse the right subtree by recursively calling the post-order function. Postorder traversal is also useful to get the postfix expression of an expression tree. It is used in compiler design as well.

Example

In the above tree the postorder (green bubble) sequence is: A, C, E, D, B, H, I, G, F

C++ Code

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void PrintPostorder(int Nodes[],int start,int end){
    if(start>end)
        return;
    PrintPostorder(Nodes,start*2+1,end);   //Executing the left subtree
    PrintPostorder(Nodes,start*2+2,end);   //Executing the right subtree
    cout<<Nodes[start]<<" ";             //Printing present value
}
int main(){
    int Tree[] = {4, 2, 6, 1, 3, 5, 7};
    int n = sizeof(Tree)/sizeof(int);
    cout<<"The Postorder Traversal is:"<<endl;
    PrintPostorder(Tree,0,n-1);
    return 0;
}

Hope you like the tutorial. Please comment if you are satisfied. Follow the blog for getting update first.