Postorder Traversal in a Binary Tree

Postorder Traversal is done by traversing the left and right child nodes of a node binary tree or subtree before the node. In short it is termed as Left-Right- Root. The Postorder Traversal process in Binary Trees can be done by recursive and non recursive methods as we did in Preorder and Inorder traversal techniques.

Recursive Traversal

In recursive Postorder traversal the address of current node is stored in a pointer CURR. CURR pointer is initialized to the Root of the binary tree.

In all the subsequent recursive calls the CURR->LEFT or CURR->RIGHT nodes are passed as the last argument. The node passed as last argument becomes the root for the subtree that is currently being traversed.

The traversal procedure is repeatedly called for left and right child nodes till CURR (pointer storing address of current node) becomes NULL.

Algorithm REC_TRAVERSAL(DATA, LEFT, RIGHT, ROOT)
1.	[ Initialize Pointer]  CURR=ROOT
2.	IF CURR <>NULL
    a.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->LEFT)
    b.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->RIGHT)
    c.	Process node CURR
3.	Exit

Non-Recursive Traversal

In non-recursive Postorder Traversal an intermediary storage data structure Stack is used to store the nodesthat have still to be processed.

Traversal begins from the root node. The current node is pushed on the stack. If the current node has a right child node it is also pushed in the stack by adding ‘-‘ before it. This symbol before it is used to identify that it is a right subtree of a node that has been deferred while moving from root to leftmost leaf node.

When leaf node is reached, backtracking is used to pop the pending nodes and process them. If a node is preceded by “-“ symbol it is treated as a subtree and the process of storing its leftmost branch in stack begins again. If a node is not preceded by “-“ symbol, then it is processed.

Algorithm NONREC_TRAVERSAL (DATA, LEFT, RIGHT, ROOT)
1.	[Initialize variables and stack] TOS=1, STK[TOP]=# , CURR=ROOT
2.	[store leftmost  branch in stack and and every right child with "-" symbol]
    Repeat steps 3, 4 and 5 while CURR<> NULL
3.	TOS=TOS+1  [Push current node in stack]
    STK[TOS]=CURR
4.	[If Right child node is existing for current node store it in the stack]
    TOS=TOS+1
    STK[TOS]=-CURR->RIGHT
5.	[update CURR with child node ]
    CURR= CURR->LEFT
6.	[pop from stack and store in CURR to begin backtracking]
    CURR=STK[TOS]      TOS=TOS-1
7.	Repeat while CURR is positive
    a.	Process node CURR
    b.	CURR=STK[TOS]       , TOS=TOS-1
8.	If CURR is negative
    a.	CURR=-CURR
    b.	GOTO step2
9.	END

Postorder Traversal of Arithmetic Expression Tree

Like preorder traversal Postorder Traversal is also used for converting an arithmetic expression stored in a binary tree into postfix notation. Postfix notation is also called Reverse Polish Notation wherein a Binary Operator follows the operands that it operates on.

Consider the following expression-

A+B

Its Postfix Notation or Reverse Polish Notation is AB+.

An arithmetic binary expression represented in an expression tree can be traversed in Postorder and Prefix expression can be generated.

The following image shows an expression tree made from the binary expression (a+b)*(c-d)

Its Postorder traversal generates this output.

ab+cd-*

admin