Trusted answers to developer questions

What is post-order traversal?

Get Started With Data Science

Learn the fundamentals of Data Science with this free course. Future-proof your career by adding Data Science skills to your toolkit — or prepare to land a job in AI, Machine Learning, or Data Analysis.

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.

Basic Algorithm

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).

  1. Recursively traverse the left subtree.
  2. Recursively traverse the right subtree.
  3. Visit the root.
1 of 12

For an n-ary tree:

  1. Traverse the subtrees from left to right.
  2. Visit the root node.
1 of 18

Implementation in C++

The following code snippet implements post-order traversal for a binary tree.

#include <iostream>
using namespace std;
struct Tree
{
char data;
Tree *left;
Tree *right;
Tree(char data)
{
this -> data = data;
left = NULL;
right = NULL;
}
};
void PostOrderTraversal(Tree *node)
{
if(node == NULL){
return;
}
else{
PostOrderTraversal(node -> left);
PostOrderTraversal(node -> right);
cout << node -> data << ", ";
}
}
int main() {
Tree *root = new Tree('a');
root -> left = new Tree('b');
root -> right = new Tree('c');
root -> left -> left = new Tree('d');
root -> left -> left -> left = new Tree('e');
root -> left -> left -> right = new Tree('f');
PostOrderTraversal(root);
return 0;
}

RELATED TAGS

data structure
tree
traversal
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?