Your Position: Home - Hardware - What is post-order traversal?
Tree traversal refers to visiting all the nodes of a tree exactly once. Visiting means doing something to the node. It can be as basic as printing the node.
Post-order traversal is one of the multiple methods to traverse a tree. It is mainly used for tree deletion.
The following algorithm is specific to a binary tree but can be generalized to an n-ary tree (a tree where each node can have at most n children nodes).
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways.
A Tree Data Structure can be traversed in following ways:
- Depth First Search or DFS
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal or Breadth First Search or BFS
- Boundary Traversal
- Diagonal Traversal
Algorithm Inorder(tree)
- Traverse the left subtree, i.e., call Inorder(left->subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right->subtree)
In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
Code implementation of Inorder traversal.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Inorder traversal of binary tree is \n");
printInorder(root);
getchar();
return 0;
}
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(struct Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Inorder traversal of binary tree is \n";
printInorder(root);
return 0;
}
Java
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() { root = null; }
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.key + " ");
printInorder(node.right);
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root =