Preorder, inorder, postorder (recursive code and hand tracing)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• In a 1-based array tree, where are the children of node i? from Lesson 4.2.3
• Define a strict binary tree. from Lesson 4.2.1
• In recursion, when does code written after the recursive call run? from Lesson 2.1.2

1 · The Hook

🎣

A school inspector must visit every classroom in a building whose wings branch into sub-wings. She can note a wing’s name when she first enters it, after finishing its left part, or after finishing the whole wing. Each choice produces a different list, and each list is useful for something different.

2 · Predict First

🤔

For the example tree (1 at the root; 2 and 3 its children; 4, 5 under 2; 7 under 5 on the left; 6 under 3 on the right), what does printing “node, then left subtree, then right subtree” give? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1 2 4 5 7 3 6 (preorder). The root comes first, then the whole left side, then the whole right side.

Three recursive orders

Each visits the root and recursively both subtrees; they differ only in when the root is printed:

void pre(struct tnode *t)  { if (t == NULL) return; printf("%d ", t->data); pre(t->left); pre(t->right); }
void in(struct tnode *t)   { if (t == NULL) return; in(t->left); printf("%d ", t->data); in(t->right); }
void post(struct tnode *t) { if (t == NULL) return; post(t->left); post(t->right); printf("%d ", t->data); }

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    pre(root);  printf("\n");
    in(root);   printf("\n");
    post(root); printf("\n");
    return 0;
}

Output

1 2 4 5 7 3 6 
4 2 7 5 1 3 6 
4 7 5 2 6 3 1

Hand tracing trick

Walk around the tree outline counter-clockwise starting left of the root, touching every node three times: from the left side, from below, from the right side. Writing a node on its first touch gives preorder, on its second (from below) inorder, on its third postorder.

Facts worth remembering

• Preorder starts with the root; postorder ends with it.
• Inorder places the root between its left and right subtrees.
• Each traversal is O(n) time; the recursion depth is the height + 1 (O(n) for a skewed tree).
• The first node in inorder is the leftmost node; the last in preorder is the last leaf reached going right where possible.

Mixed traversals in code

GATE often mixes the orders inside one function. Treat each printf as before/between/after the calls, as in Lesson 2.1.2:

void f(struct tnode *t)
{
    if (t == NULL) return;
    printf("%d ", t->data);
    f(t->right);
    printf("%d ", t->data);
    f(t->left);
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, NULL, NULL), mk(3, mk(4, NULL, NULL), NULL));
    f(root);
    printf("\n");
    return 0;
}

Output

1 3 3 4 4 1 2 2

4 · Visual

Under each node: its position in preorder / inorder / postorder.

Euler walk around the outline (touch each node 3 times):

             1
           /   \
          2     3
         / \     \
        4   5     6
           /
          7

 touches: 1 2 4 4 4 2 5 7 7 7 5 5 2 1 3 3 6 6 6 3 1
 first touch  (pre):  1 2 4 5 7 3 6
 second touch (in):   4 2 7 5 1 3 6
 third touch  (post): 4 7 5 2 6 3 1

One walk, three orders.

5 · Worked Examples

Example 1 Easy

Give the preorder, inorder and postorder of the tree below.

Tree for Example 1.

Solution

Pre: A B D E G H C F I. In: D B G E H A C I F. Post: D G H E B I F C A.

Example 2 Medium

In any binary tree, which node comes first in inorder, and which node comes last in preorder?

Solution

Inorder starts at the leftmost node: keep going left from the root until there is no left child. Preorder ends at the last node reached by preferring right children: from the root keep going right if possible, otherwise left, until a leaf. In the example tree: first in inorder 4, last in preorder 6.

Example 3 GATE

What does this print?

void f(struct tnode *t)
{
    if (t == NULL) return;
    printf("%d ", t->data);
    f(t->right);
    printf("%d ", t->data);
    f(t->left);
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, NULL, NULL), mk(3, mk(4, NULL, NULL), NULL));
    f(root);
    printf("\n");
    return 0;
}

Solution

f(1): print 1, f(3): [print 3, f(NULL), print 3, f(4): [print 4, print 4]], print 1, f(2): [print 2, print 2]. Careful: f prints, goes right first, prints again, then goes left.

Output

1 3 3 4 4 1 2 2

6 · GATE Traps

⚠️

• Preorder = root first; postorder = root last; inorder = root in the middle.
• A modified traversal may visit right before left; read the code.
• When a printf appears twice, each node is printed twice.
• Traversals visit each node once: O(n); recursion depth = height + 1.
• The inorder sequence alone does not determine the tree.

8 · Memory Hook

🧠

“PRE: I speak first. IN: I speak between my children. POST: I speak last.”

9 · Connect the Dots

Lesson 4.3.1 visited trees branch by branch, using the call stack. Sometimes we need all nodes of level 0, then level 1, and so on — the order in which a building is evacuated floor by floor. Next lesson answers: which data structure from Phase 3 produces that floor-by-floor order?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPreorder

Preorder of the tree in Example 1 is:

• (A) D G H E B I F C A
• (B) D B G E H A C I F
• (C) A B C D E F G H I
• (D) A B D E G H C F I

Q2MCQ2 marksOutput

What does this print? (the example tree, as in the lesson)

void pre(struct tnode *t)  { if (t == NULL) return; printf("%d ", t->data); pre(t->left); pre(t->right); }
void in(struct tnode *t)   { if (t == NULL) return; in(t->left); printf("%d ", t->data); in(t->right); }
void post(struct tnode *t) { if (t == NULL) return; post(t->left); post(t->right); printf("%d ", t->data); }

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    pre(root);  printf("\n");
    in(root);   printf("\n");
    post(root); printf("\n");
    return 0;
}

• (A) three lines: pre, in, post as in the table
• (B) in, pre, post
• (C) three identical lines
• (D) pre, post, in

Q3MCQ1 markRoot position

In which traversal is the root always the last node listed?

• (A) inorder
• (B) postorder
• (C) preorder
• (D) none

Q4NAT2 marksOutput

How many numbers does this print?

void f(struct tnode *t)
{
    if (t == NULL) return;
    printf("%d ", t->data);
    f(t->right);
    printf("%d ", t->data);
    f(t->left);
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, NULL, NULL), mk(3, mk(4, NULL, NULL), NULL));
    f(root);
    printf("\n");
    return 0;
}

Numerical answer: ________

Q5MSQ1 markFacts

Which are true?

• (A) Inorder of any binary tree is sorted.
• (B) Preorder lists a node before all its descendants.
• (C) The recursion depth is at most height + 1.
• (D) Each traversal visits every node once.

11 · Rule Card

• Preorder: root, L, R. Inorder: L, root, R. Postorder: L, R, root.
• Euler walk: 1st touch pre, 2nd in, 3rd post.
• O(n) time; depth = height + 1.
• Read mixed traversals statement by statement (before/between/after calls).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

tree traversalpreorderinorderpostorderEuler walk trickrecursive (branch-first) order

13 · Answer Vault