Page 228 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

The figure 12.4 depicts the functioning of postorder traversal. The figure represents the functionality of
postorder traversal.

Figure 12.4: Postorder Traversal

The algorithm for postorder traversal is as follows:
Input – ROOT is the pointer to the root node of binary tree
Output – Visiting all nodes in postorder manner
Data Structure – Linked structure of binary tree
Steps
1. ptr = ROOT //Start from ROOT
2. If (ptr ≠ null) then //If it is non-empty node

3. Postorder (ptrllink) //Traverse left sub-tree of node in postorder
manner
4. Postorder (ptrrlink) //Traverse right sub-tree of node in postorder
manner
5. Visit (ptr) //Visit the node
6. EndIf
7. Stop

Consider the binary tree shown in the figure 12.2. The postorder traversing
depends on traversing first the left sub-tree, right sub-tree and then the node.
Since, the traversing process starts with the left sub-tree, right sub-tree and root
node, let us consider the alphabets L, R, N for postorder traversal.
The term T1 LRNindicates that node T1 is the root node of the binary tree and
subscript LRN indicates postorder tree traversal.

T1 LRN---->T2 LRNT3 LRNT1 //After visiting T1 LRN

---->T4 LRN µ T2 T3 LRNT1//After visiting T2 LRN
---->T7 LRN T8 LRNT4 T2 T3 LRNT1//After visiting T4 LRN
---->µµT7 T8 LRNT4 T2 T3 LRN T1//After visiting T7 LRN

---->T7 µµT8 T4T2 T3 LRNT1//After visiting T8 LRN
---->T7 T8 T4 T2 T5 LRN T6 LRNT3T1//After visiting T3 LRN

LOVELY PROFESSIONAL UNIVERSITY 221