DSA Post-order Traversal
Post-order Traversal of Binary Trees
A variation of Depth First Search called Post-order Traversal visits each node in a certain sequence. Go here to learn more about traversals of binary trees in general.
This is an example of how to conceptualize doing a Post-order Traversal on a Binary Tree:
==== example mukavu ====
In order for Post-order Traversal to function, the left and right subtrees must be traversed recursively, and then the root node must be visited. It can be used to delete trees, post-fix notation of expression trees, and other things.
The fact that a node visit occurs “after” the left and right child nodes are called recursively is what distinguishes this traversal as “post”.
The Post-order Traversal code looks like this:
Example
Python:
def postOrderTraversal(node):
if node is None:
return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print(node.data, end=", ")
When C’s left child node is called with the node parameter, the postOrderTraversal() method continues recursively traversing the left subtree (line 4) until None is returned.
Line 5 continues and C’s right child node returns None after C’s left child node returns None. The letter ‘C’ is then printed (line 6).
This is why “post” order traversal is used: it indicates that C is visited, or printed, “after” its left and right child nodes are traversed.
‘D’ is the next node to be written, followed by ‘A’, as the postOrderTraversal() function keeps propagating back to earlier recursive function calls.
Till every node is printed or visited, the function keeps propagating back and printing nodes.
