For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be
less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater
than the data of the root. This example shows the implementation of a binary search tree post-order traversal (depth first).
What is post-order traversal (depth first)?
Tree traversal means we visiting all nodes in the tree, visiting means either of accessing node data or processing node data.
Traversal can be specified by the order of visiting 3 nodes, ie current node, left subtree and right subtree. In post-order traversal, first we
visit the left subtree, then the right subtree, and then current node. In our current example we
use recursive approach to implement post-order traversal.
Post-order: A, C, E, D, B, H, I, G, F.
Here is an example picture of binary search tree (BST) for our example code:
Here is the steps to implement post-order traversal:
- Start with root node.
- Check if the current node is empty / null.
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).