C Binary Tree Traversal: Inorder, Preorder, Postorder

Inorder (left, root, right) — visits BST in sorted order. Preorder (root, left, right) — for serializing/copying. Postorder (left, right, root) — for deleting/freeing.

Three depth-first traversals; the only difference is when you visit the node relative to its children. Each has natural use cases.

The three traversals

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int data;
  struct Node *left;
  struct Node *right;
} Node;

void inorder(Node *root) {
  if (root == NULL) return;
  inorder(root->left);
  printf("%d ", root->data);
  inorder(root->right);
}

void preorder(Node *root) {
  if (root == NULL) return;
  printf("%d ", root->data);
  preorder(root->left);
  preorder(root->right);
}

void postorder(Node *root) {
  if (root == NULL) return;
  postorder(root->left);
  postorder(root->right);
  printf("%d ", root->data);
}

Same tree:

        50
       /  \
      30   70
     / \   /
    20 40 60

Output:

Inorder:   20 30 40 50 60 70
Preorder:  50 30 20 40 70 60
Postorder: 20 40 30 60 70 50

Inorder: left, root, right

void inorder(Node *root) {
  if (root == NULL) return;
  inorder(root->left);
  printf("%d ", root->data);   // visit root in the middle
  inorder(root->right);
}

For a BST, this produces sorted ascending order. The smallest value is the leftmost leaf; we visit left subtrees before their roots.

Use cases:

• Print BST in order. Verify it's sorted.
• Convert BST to sorted array. Append to array during traversal.
• Range queries. Stop traversal once value exceeds range.

For descending order, swap left and right:

void inorder_desc(Node *root) {
  if (root == NULL) return;
  inorder_desc(root->right);
  printf("%d ", root->data);
  inorder_desc(root->left);
}

Preorder: root, left, right

void preorder(Node *root) {
  if (root == NULL) return;
  printf("%d ", root->data);   // visit root first
  preorder(root->left);
  preorder(root->right);
}

Use cases:

• Serialize a tree. Write each node before its children — the structure can be reconstructed.
• Copy a tree. Allocate the root, then recurse to copy left and right.
• Expression-tree printing in prefix notation. (+ 2 3) style.

Node *clone(Node *root) {
  if (root == NULL) return NULL;
  Node *copy = create_node(root->data);
  copy->left = clone(root->left);
  copy->right = clone(root->right);
  return copy;
}

The clone visits root first (allocate), then children. That's preorder.

Postorder: left, right, root

void postorder(Node *root) {
  if (root == NULL) return;
  postorder(root->left);
  postorder(root->right);
  printf("%d ", root->data);   // visit root last
}

Use cases:

• Free a tree. Free children before the parent (otherwise the parent's pointers to them are lost).
• Compute tree-wide aggregates. Sum, max — process children first to know subtree values.
• Postfix-notation expression trees. 2 3 + style.

void free_tree(Node *root) {
  if (root == NULL) return;
  free_tree(root->left);
  free_tree(root->right);
  free(root);
}

The free visits children first, then the root. Critical: if you free the root first, you've lost the pointers to children → leak.

Choosing the right traversal

Level-order (BFS) traversal

A fourth pattern: visit by level, not depth. Uses a queue, not the call stack.

#include <stdlib.h>

void level_order(Node *root) {
  if (root == NULL) return;

  Node *queue[1000];
  int front = 0, rear = 0;

  queue[rear++] = root;
  while (front < rear) {
    Node *current = queue[front++];
    printf("%d ", current->data);
    if (current->left) queue[rear++] = current->left;
    if (current->right) queue[rear++] = current->right;
  }
}

Output for our tree: 50 30 70 20 40 60 — root, then row 2, then row 3.

Useful for printing trees layer by layer, or for breadth-first searches.

Iterative traversals

Recursive is natural; iterative is sometimes needed (avoiding stack overflow).

Iterative inorder:

void inorder_iter(Node *root) {
  Node *stack[100];
  int top = -1;
  Node *current = root;

  while (current != NULL || top >= 0) {
    while (current != NULL) {
      stack[++top] = current;
      current = current->left;
    }
    current = stack[top--];
    printf("%d ", current->data);
    current = current->right;
  }
}

Push all left ancestors, pop and visit, then go right.

Iterative preorder is simpler — push, pop, print, push children:

void preorder_iter(Node *root) {
  if (root == NULL) return;
  Node *stack[100];
  int top = -1;
  stack[++top] = root;

  while (top >= 0) {
    Node *current = stack[top--];
    printf("%d ", current->data);
    if (current->right) stack[++top] = current->right;
    if (current->left) stack[++top] = current->left;
  }
}

Push right before left so left is popped first.

Same shape, three orderings

The only difference between in/pre/post is which line printf is on:

• Before both recursions → preorder.
• Between them → inorder.
• After both → postorder.

This is a common interview question — being able to write all three from memory shows comfort with recursion and tree traversal.

Common mistakes

Wrong order in free. Freeing the root first crashes when recursing into freed children. Always postorder.

Recursive depth = tree height. A degenerate (line-shaped) tree of 10,000 nodes blows the stack. Iterative for huge inputs.

Confusing in-order with sorted only for BSTs. In-order traversal produces sorted output only for binary search trees, not arbitrary binary trees.

Visiting the same node twice. Bug in recursive logic — for example, inorder(root); inorder(root->left); double-counts.

Off-by-one in queue traversal. Front and rear management — keep them consistent.

What's next

Episode 52: binary search tree (BST) — full operations. Search, insert, delete (with the three deletion cases).

Recap

Three depth-first traversals: preorder (root first), inorder (root middle), postorder (root last). For BST: inorder gives sorted output. For freeing: always postorder (children before parent). For copying/serializing: preorder. For computing aggregates: postorder. Level-order is a fourth pattern using a queue, not the call stack — visits row by row. Iterative versions exist using an explicit stack.

Next episode: BST in detail.