Data Structures and Algorithms - Old Questions
8. What is Post-order traversal?
Post-order traversal is one of the multiple methods to traverse a tree.
In
Post-Order traversal, the root node is visited after left child and right
child. In this traversal, left child node is visited first, then its right
child and then its root node. This is recursively performed until the right
most node is visited.
Algorithm:
|
Until all nodes are traversed:- Step 1: Recursively traverse left
sub-tree. Step 2: Recursively traverse right
sub-tree. Step 3: Visit root node |
E.g.
The post-order traversal output of the given above tree is: H I D E B F G C A
C function for
post-order traversing:
Let pRoot is a given pointer to a root node of a binary tree.
void
post-order(BiNodeType *pRoot)
{
if(root!=NULL)
{
postorder(pRoot->left);
postorder(pRoot->right);
printf(“%d”,
pRoot->info);
}
}