I was looking for a code snippet that performs well and is simple to customise. Threaded trees are not “simple”. Double stack solution requires O(n) memory. LeetCode solution and solution by tcb have extra checks and pushes...
Here is one classic algorithm translated into C that worked for me:
void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
TreeNode *stack[40]; // simple C stack, no overflow check
TreeNode **sp = stack;
TreeNode *last_visited = NULL;
for (; p != NULL; p = p->left)
*sp++ = p;
while (sp != stack) {
p = sp[-1];
if (p->right == NULL || p->right == last_visited) {
visit(p);
last_visited = p;
sp--;
} else {
for (p = p->right; p != NULL; p = p->left)
*sp++ = p;
}
}
}
IMHO this algorithm is easier to follow than well performing and readable wikipedia.org / Tree_traversal pseudocode. For glorious details see answers to binary tree exercises in Knuth’s Volume 1.