Postorder Traversal

Postorder traversal is defined as follows:

Procedure: Postorder Traversal. Let ${B}$ be a binary tree. To traverse ${B}$ in postorder:

1. Traverse the left subtree postorder.
2. Traverse the right subtree postorder.
3. Visit the node.

In pseudocode:

fn postorder_traverse(tree):
	postorder_traverse(left_subtree);
	postorder_traverse(right_subtree);
	visit(node);

We illustrate with a binary tree of order ${3:}$

We start by calling postorder_traverse() with n(a) the root, as an argument. I.e., we call postorder_traverse(tree: n(a)). Calling this function, results in the recursive call postorder_traverse(left_subtree: n(a)). Because the left subtree of n(a) has as its root n(a) the call postorder_traverse(left_subtree: n(a)) is actually the call postorder_traverse(tree: n(b)). That call then results in calling postorder_traverse(left_subtree: n(b)). But because n(b) has no left subtree, we go to the next call, postorder_traverse(right_subtree: n(b)). But there is no right subtree of n(b) so we call visit(node: n(b)).

This finishes the call postorder_traverse(left_subtree: n(a)), so we call postorder_traverse(right_subtree: n(a)). Because the right subtree of n(a) has the root n(c) the call is actually postorder_traverse(tree: n(c)). Thus, we call postorder_traverse(left_subtree: n(c)) and postorder_traverse(right_subtree: n(c)), but because n(c) has neither left nor right subtrees, we call visit(n(c)).

This finishes the call postorder_traverse(right_subtree: n(a)). All that's left to do is call visit(node: n(a)).

Summarizing, the traversal sequence for a binary tree of order ${3}$ is:

If the binary tree was left-skewed, the traversal sequence would be ${(n_b, n_a).}$

If the binary tree was right-skewed, the traversal sequence would be ${(n_c, n_a).}$

fn postorder(Node* root) -> void:
	postorder((*root).left_child)
	postorder((*root).right_child)
	print((*root).data)