Postorder Traversal of binary trees

Last Updated on

To postorder a non-empty binary tree, below operations are preformed recursively of each node

  1. traversing the left subtree
  2. traversing the right subtree
  3. visiting the root node
Postorder Traversal of binary trees 1

the word “post” specifies that the root node is accessed last to any other node from the left and right subtrees

lets see one example:

Postorder Traversal of binary trees 2

step 1: currently search pointer is pointed to the node A, root node is now node A, the first priority is the left subtree, so search pointer moves to node B, but node B has left subtree, search pointer goes to the leaf node G, because there is no sub-nodes to node G, now this node G will be accessed

Postorder Traversal of binary trees 3

step 2: search pointer goes to the leaf node G, because there is no sub-nodes to node G, now this node G will be accessed , search pointers goes back to parent node D

Postorder Traversal of binary trees 4

step 3:search pointer i snow at node D,node D is root node ,postorder operation is applied on the left subtree of node D ,next the priority goes t the right sub tree H and accessed it ,H doesn’t have any sub-nodes,search pointer goes back to parent node D and root node D will be accessed at the last according to priority order

Postorder Traversal of binary trees 5

step 4:search pointer will be moved from node D to the node B because node B is the parent node of node D and grandparent node of node H ,now root is at node B ,post order operation is done on the left sub tree of the node B,next priority is right subtree, node B’s right subtree contains single node E,this node E will be accused ,node E is doesn’t have any sub-trees so search pointer moves back to node B and access it because postorder operations are completed on both subtrees

Postorder Traversal of binary trees 6

step 5:search pointer is at node A,postorder operation is completed for left subtree B and according to priority next will be right subtree (node C)

Postorder Traversal of binary trees 7

step 6:serach pointer moves from node A to C , and at node C there is a left sub-tree F, search pointer movies to node F,now node F is the root node ,there is no left subtree for node F ,next priority goes to right subtree node I and node I will be accessed ,node I doesnt have any subnodes so search pointer moves to the parent node F , after; left and right subtrees next priority goes to root node F, so node F will be accessed

Postorder Traversal of binary trees 8

step 7:search pointer goest to the node C because thts the parent node for node F,now root node is node C,postorder operation is completed for the left subtree F,then next priortity is right sub tree but there is no rigjht sub tree ,so next eill wil be root node C

Postorder Traversal of binary trees 9

step 8: pointer goes to the node A because this the parent node for node C,now root node is node A, post order operation is complete for both left and right subtrees of the node A, next priority will be itself root node A, so now root node A will be accessed