Recursive algorithms

1. Preorder: if node exists, visit it, traverse left, traverse right.
2. Inorder: traverse left, visit the node, traverse right.
3. Postorder: traverse left, traverse right, visit the node.
4. For a NULL subtree, return without visiting.

Worked example

For root 1, children 2 and 3, and children 4 and 5 under node 2: preorder is 1 2 4 5 3; inorder is 4 2 5 1 3; postorder is 4 5 2 3 1. The complete example prints these orders.

Iterative alternative

For inorder without recursion, use an explicit node-pointer stack. Push nodes while moving left. When no left node remains, pop and visit one, then move to its right subtree. Repeat while either the current node exists or the stack is non-empty. The stack replaces the pending recursive calls.

Applications

Preorder can describe a parent before descendants. Postorder is useful when children must be handled before a parent, including tree destruction. Inorder gives increasing keys for a BST with its stated ordering policy, but not for every arbitrary binary tree.

Complexity

Each node is visited once, so time is O(n). Recursive call depth is O(h), where h is tree height; it becomes O(n) for a chain. An explicit traversal stack has the corresponding height-dependent storage. A NULL root produces no values.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
struct Node { int key; struct Node *left, *right; };
void preorder(const struct Node *p) { if (p != NULL) { printf("%d ", p->key); preorder(p->left); preorder(p->right); } }
void inorder(const struct Node *p) { if (p != NULL) { inorder(p->left); printf("%d ", p->key); inorder(p->right); } }
void postorder(const struct Node *p) { if (p != NULL) { postorder(p->left); postorder(p->right); printf("%d ", p->key); } }

int main(void)
{
    struct Node n4 = {4, NULL, NULL}, n5 = {5, NULL, NULL};
    struct Node n2 = {2, &n4, &n5}, n3 = {3, NULL, NULL}, root = {1, &n2, &n3};
    printf("Preorder: "); preorder(&root); putchar('\n');
    printf("Inorder: "); inorder(&root); putchar('\n');
    printf("Postorder: "); postorder(&root); putchar('\n');
    return 0;
}

Preorder: 1 2 4 5 3 
Inorder: 4 2 5 1 3 
Postorder: 4 5 2 3 1