Self-checkedTier 1 19 min readpds.binary-tree-traversals

Binary tree traversals

The four ways to visit every node of a binary tree (preorder, inorder, postorder, level order), how to read each off a drawing by hand, how the recursion and the explicit stack or queue really work, how many calls they make, and the facts about the three depth-first orders that exam questions use.

Why it exists

A list has one natural order. A tree has none: after visiting a node you must decide whether to deal with the node itself, its left subtree or its right subtree first. The choice gives different orders, and each one is useful: inorder gives the keys of a search tree in sorted order, preorder copies a tree, postorder frees a tree or evaluates an expression, level order finds the nearest nodes first. Questions ask for these orders, ask which tree produces a given order, and ask about the work done to produce them.

Prerequisites

Trees and binary trees Stack (abstract data type)Recursion and the call stack

Precise definitions

For a binary tree with root $N$ , left subtree $L$ and right subtree $R$ , the three depth-first orders are defined recursively. An empty tree produces no output.

Order	Rule	Memory aid
Preorder	visit $N$ , then preorder of $L$ , then preorder of $R$	root first
Inorder	inorder of $L$ , then visit $N$ , then inorder of $R$	root in the middle
Postorder	postorder of $L$ , then postorder of $R$ , then visit $N$	root last
Level order	all nodes at depth 0, then depth 1, then depth 2, ..., each level left to right	breadth first

The left subtree is always done before the right one. Only the position of the root changes.

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

Preorder moves the printf before the first call; postorder moves it after the second.

Reading the orders from a drawing

Walk around the outside of the tree, starting at the root and keeping the tree on your left, so that you pass every node three times: on the way down into it, between its subtrees, and on the way back up.

Preorder lists a node the first time you meet it (just before you go into the left subtree).
Inorder lists it the second time (after the left subtree, before the right one). A leaf is passed all three times at once.
Postorder lists it the third time (after both subtrees).

Level order

Use a queue (see the queue page). Put the root in the queue. While the queue is not empty: remove the front node, visit it, and add its left then right child (if any) at the rear. The queue always holds the nodes of one level followed by some of the next.

Cost

Every depth-first traversal visits each node once. A tree with $n$ nodes causes $n$ calls on nodes and $n + 1$ calls on NULL, $2n + 1$ calls in all, so the time is $\Theta(n)$ .
The stack holds at most $h + 1$ frames for real nodes (one more, $h + 2$ , while a call on NULL is running): $\Theta(\log n)$ for a balanced tree, but $\Theta(n)$ for a chain.
Level order uses a queue that can hold a whole level, up to about $n/2$ nodes.

Facts about the three orders

In preorder an ancestor always comes before its descendants. In postorder an ancestor always comes after its descendants. In inorder there is no such rule.
If two nodes $u$ and $v$ are in different subtrees of their lowest common ancestor, with $u$ in the left one and $v$ in the right one, then $u$ comes before $v$ in all three orders.
The leaves appear in the same left to right order in preorder, inorder and postorder.
A binary search tree (see BST) printed inorder is sorted.
For an expression tree, preorder gives the prefix form, inorder the infix form (without brackets), and postorder the postfix form.
The preorder of a tree is the reverse of the postorder of its mirror image (left and right swapped everywhere).
Which pairs of traversals determine the tree is on the next page.

How it works

All four animations use the same tree: root 1; node 2 has children 4 and 5; node 5 has left child 7; node 3 has right child 6. The picture is drawn from the program's real pointers and the "printed so far" row is what the shown printf really printed. A node is marked with its print order (a green badge) once it has been printed, and the call stack is shown in blue.

Preorder

The node is printed on entry, before either subtree. Notice that when the call on node 4 returns, nothing is left to do for it: the print already happened.

Preorder traversal: node, left, right

Real run

C source

1#include <stdio.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8void preorder(struct node *t) {

9 if (t == NULL)

10 return;

11 printf("%d ", t->data);

12 preorder(t->left);

13 preorder(t->right);

14}

Tree (read from the program's real pointers)

Recursive calls in progress (oldest on the left)

Printed so far

nothing yet

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

call on node 1

1 / 29

The tree (root 1; 2 has children 4 and 5; 5 has left child 7; 3 has right child 6) is built by setup code that is not shown. The function shown is the exact code that runs. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Inorder

The print sits between the two recursive calls. Node 2 is printed after its whole left subtree (4) and before its right subtree (5, 7). Look at how a NULL call (returning at once) separates a node from a missing child.

Inorder traversal: left, node, right

Real run

C source

1#include <stdio.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8void inorder(struct node *t) {

9 if (t == NULL)

10 return;

11 inorder(t->left);

12 printf("%d ", t->data);

13 inorder(t->right);

14}

Tree (read from the program's real pointers)

Recursive calls in progress (oldest on the left)

Printed so far

nothing yet

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

call on node 1

1 / 29

Postorder

The node is printed last. The root 1 is the final item, and a node is never printed before its descendants.

Postorder traversal: left, right, node

Real run

C source

1#include <stdio.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8void postorder(struct node *t) {

9 if (t == NULL)

10 return;

11 postorder(t->left);

12 postorder(t->right);

13 printf("%d ", t->data);

14}

Tree (read from the program's real pointers)

Recursive calls in progress (oldest on the left)

Printed so far

nothing yet

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

call on node 1

1 / 29

Level order

There is no recursion here. The amber nodes are in the queue, which is shown in order, front on the left. A node is printed when it leaves the queue, and its children join at the rear.

Level-order traversal with a queue

Real run

C source

1#include <stdio.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8void levelorder(struct node *root) {

9 struct node *q[16];

10 int front = 0, rear = 0;

11 if (root == NULL)

12 return;

13 q[rear++] = root;

14 while (front < rear) {

15 struct node *t = q[front++];

16 printf("%d ", t->data);

17 if (t->left)

18 q[rear++] = t->left;

19 if (t->right)

20 q[rear++] = t->right;

21 }

22}

Tree (read from the program's real pointers)

Queue (front on the left)

Printed so far

nothing yet

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

put the root in the queue

1 / 22

The tree (root 1; 2 has children 4 and 5; 5 has left child 7; 3 has right child 6) is built by setup code that is not shown. The function shown is the exact code that runs. The queue is the array q in the shown code. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1The three depth-first orders

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    in(t->left);
    printf("%d ", t->data);
    in(t->right);
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    printf("%d ", t->data);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    pre(r);
    printf("\n");
    in(r);
    printf("\n");
    post(r);
    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

Reading it. The same tree gives three different orders, and the only difference between the three functions is where the printf sits. Check with the walk-around rule: node 2's first visit comes right after 1 (preorder 1 2), its second visit is after 4 (inorder 4 2), and its third visit is after its right subtree finishes (postorder ... 5 2).

EX 2Inorder without recursion: an explicit stack

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int deepest;
 
static void inorder_iter(const struct node *t) {
    const struct node *st[16];
    int top = -1;
    while (t != NULL || top >= 0) {
        while (t != NULL) {
            st[++top] = t;
            if (top + 1 > deepest) deepest = top + 1;
            t = t->left;
        }
        t = st[top--];
        printf("%d ", t->data);
        t = t->right;
    }
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    inorder_iter(r);
    printf("\n%d\n", deepest);
    return 0;
}

Output:

4 2 7 5 1 3 6
3

Reading it. The inner loop walks as far left as possible, pushing every node it passes: these are the nodes whose left subtree is not finished yet (exactly the pending recursive calls). The pop takes the most recently pushed node, prints it, and moves to its right subtree. The stack never holds more than 3 nodes. It holds the nodes whose left subtree is still being worked on, which is most of the information the recursion keeps in its frames, so the space is $O(h)$ . (The recursive version has 4 frames for real nodes alive at its deepest point, nodes 1, 2, 5 and 7, because a frame stays until its call returns; a call on NULL adds one more briefly. The saving here is specific to this tree: on a left chain the two versions need the same amount. The explicit stack drops node 2 when it is printed, since the only work left for 2 is its right subtree, which the variable t carries.)

EX 3Level order, one level at a time

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static void levels(const struct node *root) {
    const struct node *q[16];
    int f = 0, r = 0;
    if (root == NULL)
        return;
    q[r++] = root;
    while (f < r) {
        int n = r - f;
        for (int i = 0; i < n; i++) {
            const struct node *t = q[f++];
            printf("%d ", t->data);
            if (t->left) q[r++] = t->left;
            if (t->right) q[r++] = t->right;
        }
        printf("| ");
    }
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    levels(r);
    printf("\n");
    return 0;
}

Output:

1 | 2 3 | 4 5 6 | 7 |

Reading it. At the start of each round of the while loop, the queue holds exactly one level, and n = r - f is its size. The inner loop handles those n nodes and their children join the rear for the next round. The bars mark the level boundaries: 1; 2 and 3; 4, 5 and 6; 7.

EX 4How many calls does a traversal make?

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int calls, null_calls;
 
static void walk(const struct node *t) {
    calls++;
    if (t == NULL) {
        null_calls++;
        return;
    }
    walk(t->left);
    walk(t->right);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    walk(r);
    printf("%d %d\n", calls, null_calls);
    return 0;
}

Output:

15 8

Reading it. The tree has $n = 7$ nodes, so there are $n + 1 = 8$ calls on NULL (one for every empty child slot, see the null pointer count on the trees page) and $7$ calls on real nodes: $2n + 1 = 15$ in all. The count does not depend on the order in which the node is visited, only on the tree. The deepest the stack gets is the height plus one frames for real nodes (4 here), and one more while a NULL call runs.

EX 5The leaves come out in the same order in every traversal

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int leaf(const struct node *t) {
    return t->left == NULL && t->right == NULL;
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    if (leaf(t)) printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    in(t->left);
    if (leaf(t)) printf("%d ", t->data);
    in(t->right);
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    if (leaf(t)) printf("%d ", t->data);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    pre(r);
    printf("\n");
    in(r);
    printf("\n");
    post(r);
    printf("\n");
    return 0;
}

Output:

4 7 6
4 7 6
4 7 6

Reading it. The three functions print only the leaves. Since the left subtree is always handled before the right one, and a leaf has no subtrees of its own, a leaf can only move relative to other leaves by being in a different subtree, and then the left one comes first in every order. So the leaf sequence is the same for preorder, inorder and postorder. Once you know which entries are leaves (from the tree, or from a pair of orders that fixes them), their order is the same in every list, so you can read them off whichever list is handy.

EX 6An expression tree and its three notations

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    char op;
    struct node *left, *right;
};
 
static struct node *mk(char c, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->op = c;
    t->left = l;
    t->right = r;
    return t;
}
 
static void prefix(const struct node *t) {
    if (t == NULL) return;
    putchar(t->op);
    prefix(t->left);
    prefix(t->right);
}
 
static void infix(const struct node *t) {
    if (t == NULL) return;
    infix(t->left);
    putchar(t->op);
    infix(t->right);
}
 
static void postfix(const struct node *t) {
    if (t == NULL) return;
    postfix(t->left);
    postfix(t->right);
    putchar(t->op);
}
 
static void bracketed(const struct node *t) {
    if (t->left == NULL) {
        putchar(t->op);
        return;
    }
    putchar('(');
    bracketed(t->left);
    putchar(t->op);
    bracketed(t->right);
    putchar(')');
}
 
int main(void) {
    struct node *r = mk('*', mk('+', mk('a', NULL, NULL), mk('b', NULL, NULL)),
                        mk('-', mk('c', NULL, NULL), mk('d', NULL, NULL)));
    prefix(r);
    printf("\n");
    infix(r);
    printf("\n");
    postfix(r);
    printf("\n");
    bracketed(r);
    printf("\n");
    return 0;
}

Output:

*+ab-cd
a+b*c-d
ab+cd-*
((a+b)*(c-d))

Reading it. The tree stands for $(a + b) \times (c - d)$ . Preorder gives the prefix form *+ab-cd, postorder the postfix form ab+cd-*. Plain inorder gives a+b*c-d, which, read with the usual precedence, means $a + (b \times c) - d$ , a different expression: the brackets, which the tree structure carried, are lost. This is why the infix form needs the extra brackets that the fourth function adds. Postfix and prefix need no brackets, which is what makes them easy to evaluate with a stack (see stack applications).

EX 7Preorder of the mirror image is the reverse of postorder

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int pre_a[16], post_a[16], np, nq;
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    pre_a[np++] = t->data;
    pre(t->left);
    pre(t->right);
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    post_a[nq++] = t->data;
}
 
static void mirror(struct node *t) {
    if (t == NULL) return;
    struct node *tmp = t->left;
    t->left = t->right;
    t->right = tmp;
    mirror(t->left);
    mirror(t->right);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    post(r);
    mirror(r);
    pre(r);
    int same = np == nq;
    for (int i = 0; i < np; i++) same = same && pre_a[i] == post_a[nq - 1 - i];
    for (int i = 0; i < np; i++) printf("%d ", pre_a[i]);
    printf("\n%d\n", same);
    return 0;
}

Output:

1 3 6 2 5 7 4
1

Reading it. Postorder is left, right, node. Reading it backwards gives node, right, left: a preorder in which the right subtree is visited first, which is the preorder of the mirror image. The program prints the preorder of the mirrored tree, 1 3 6 2 5 7 4, and checks that it equals the original postorder 4 7 5 2 6 3 1 read backwards. The same reasoning gives: the postorder of the mirror is the reverse of the preorder of the original.

Cheat box

Preorder $N L R$ . Inorder $L N R$ . Postorder $L R N$ . Level order: by depth, left to right (queue).
By hand: walk around the tree; list a node on the 1st (pre), 2nd (in), 3rd (post) time you pass it.
A tree with $n$ nodes: $n$ node-calls and $n + 1$ NULL-calls, $2n + 1$ in total. Time $\Theta(n)$ . Stack depth $= h + 1$ frames for real nodes.
Preorder: ancestors before descendants. Postorder: descendants before ancestors. Root is the first in preorder and last in postorder.
Nodes in the left versus right subtree of their lowest common ancestor: the left one is first in all orders.
Leaves: same order in pre, in and post.
BST inorder is sorted. Expression tree: pre = prefix, in = infix (no brackets), post = postfix.
Preorder of the mirror $=$ reverse of postorder.
Iterative traversal: an explicit stack (depth first) or queue (breadth first).

Traps and GATE patterns

Connections

Builds on

Trees and binary trees Stack (abstract data type)Recursion and the call stack

Unlocks

Recursion patternsuses Trees and binary treesuses Constructing a tree from its traversalsPrerequisite of Binary search treesPrerequisite of Stack applications: expression evaluation and matchinguses

Across subjects

BFS and DFSanalogous-to Three-address code, quadruples and triplesanalogous-to

Within this subject

Constructing a tree from its traversalsuses Binary search treesuses Queue (abstract data type)uses Recursion patternsuses

The recursion is the call stack of the earlier pages, with two recursive calls per node (see recursion patterns), and the explicit-stack version is the stack at work. Level order uses the queue, and is breadth-first search on a tree, the special case of graph traversal. In a compiler, the postorder of an expression tree is the order in which three-address code is generated.

PYQs

10 previous year questions from your book. I re-solved each one myself (9 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 1Q2 · page 66 of the book

The following sequence corresponds to the
preorder traversal of a binary search tree
T: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 .
The position of the element 60 in the post-order
traversal of T is
.

GATE 2026 · Set 2Q3 · page 66 of the book

The set T represents various traversals over binary
tree. The set S represents the order of visiting nodes
during a traversal

T
S
I : Inorder
L: left subtree, node, right
subtree
II : Preorder
M: node, left subtree, right
subtree
III : Postorder
N :  left  subtree,  right
subtree, node
Which one of the following is the correct match
from T to S?

(a)1-L, II-M, III - N
(b)I-M, II-L, III - N
(c)I-N, II-M, III - L
(d)I-L, II-N, III - M

GATE 2023Q5 · page 66 of the book

Consider the C function foo and the binary tree
shown

DATA STRUCTURE

typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p)

{
int retval;
if (p == NULL)
return 0;

else{
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
obtained by doing DFS in a connected undirected
graph G.
Which of the following options is/are correct?

(a)Root of T is an articulation point in G if and only if it has 2 or more children.
(b)A leaf of T can be an articulation point in G.
(c)Root of T can never be an articulation point in G.
(d)If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u. } When foo is called with a pointer to the root node of the given binary tree, what will it print?
(a)3 8 5 13 11 10
(b)3 5 8 10 11 13
(c)3 8 16 13 24 50
(d)3 16 8 50 24 13

GATE 2020 · MCQQ13 · page 68 of the book

The preorder traversal of a binary search tree is 15,
10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder
traversal of the tree?

(a)20, 19, 18, 16, 15, 12, 11, 10
(b)11, 12, 10, 16, 19, 18, 20, 15
(c)10, 11, 12, 15, 16, 18, 19, 20
(d)19, 16, 18, 20, 11, 12, 10, 15

GATE 2017 · MCQ · 1 markQ15 · page 68 of the book

The pre-order traversal of a binary search tree is
given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.
Then the post-order traversal of this tree is:

(a)2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
(b)2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
(c)7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
(d)7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

GATE 2016 · Set 2Q21 · page 69 of the book

Consider the following New-order strategy for
traversing a binary tree:
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree
corresponding to the reverse polish expression 3 4
* 5 - 2 ˆ 6 7 * 1 + - is given by:

(a)+ - 1 6 7 * 2 ˆ 5 - 3 4 *
(b)- + 1 * 6 7 ˆ 2 - 5 * 3 4
(c)- + 1 * 7 6 ˆ 2 - 5 * 4 3
(d)1 7 6 * + 2 5 4 3 * - ˆ -

GATE 2014Q31 · page 71 of the book

Consider the following rooted tree with the vertex
P labelled as root

GATE 2013 · MCQQ32 · page 71 of the book

The preorder traversal sequence of a binary search
tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one
of the following is the postorder traversal sequence
of the same tree?

(a)10, 20, 15, 23, 25, 35, 42, 39, 30
(b)15, 10, 25, 23, 20, 42, 35, 39, 30
(c)15, 20, 10, 23, 25, 42, 35, 39, 30
(d)15, 10, 23, 25, 20, 35, 42, 39, 30 } the appropriate expression for the two boxes B1 and B2 are
(a)B1: (1+height(n→right)) B2: (1+max(h1,h2))
(b)B1: (height(n→right) B2: (1+max(h1,h2))
(c)B1: height(n→right) B2: max(h1,h2)
(d)B1: (1+ height(n→right)) B2: max(h1,h2)

GATE 2014 · Set 3 · MCQQ43 · page 73 of the book

The inorder and preorder traversal of a binary tree
are
Inorder: d b e a f c g
Preorder: a b d e c f g
The postorder traversal of the binary tree is:

(a)d e b f g c a
(b)e d b g f c a
(c)e d b f g c a
(d)d e f g b c a

GATE 2005Q49 · page 74 of the book

Postorder traversal of a given binary search tree, T
produces the following sequence of keys:
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can
be the result of an in-order traversal of the tree T?

(a)9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(b)9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(c)29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(d)95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Self-check

Question 1

Preorder of a binary tree is A B D E C and its inorder is D B E A C. What is the postorder?

Show answer

The root is A (first of preorder). In the inorder list A splits D B E (left) from C (right). In the left part the root is B (next in preorder) which splits D from E. So A has left subtree B(D, E) and right child C. Postorder: D E B C A.

Question 2

A binary tree has 10 nodes. How many recursive calls does a preorder traversal make in total, and how many of them are on NULL?

Show answer

$2n + 1 = 21$ calls in total, of which $n + 1 = 11$ are on NULL.

Question 3

In which of preorder, inorder and postorder can a leaf appear before an ancestor of itself?

Show answer

Postorder always puts descendants before ancestors, so a leaf comes before every ancestor. In preorder an ancestor always comes first, so never. In inorder it depends: a leaf in the left subtree of its ancestor comes before it, one in the right subtree comes after.

Question 4

An expression tree gives the postfix string 5 3 2 * +. What is the prefix string and the value?

Show answer

Read postfix with a stack: 5, 3, 2, then * combines 3 2 into 3 * 2, then + combines 5 with that: the expression is $5 + (3 \times 2) = 11$ . The tree has + at the root, left child 5, right child * with children 3 and 2. Prefix: + 5 * 3 2.

Question 5

What happens to the stack depth of a recursive inorder traversal for a tree that is a chain of $n$ nodes, and for a perfect tree of $n$ nodes?

Show answer

Chain: the depth reaches $n$ (height $n - 1$ , plus one, counting frames for real nodes), so $\Theta(n)$ space and a risk of stack overflow for large $n$ . Perfect tree: height $\log_2(n + 1) - 1$ , so the depth is only $\Theta(\log n)$ .

Revision card

One-screen revision

Pre $N L R$ , in $L N R$ , post $L R N$ , level: queue by levels. Left is always before right.
Walk around the tree: 1st pass = pre, 2nd = in, 3rd = post.
$n$ nodes: $2n + 1$ calls ( $n + 1$ on NULL), $\Theta(n)$ time, $h + 1$ node frames of stack depth.
Preorder: root first, ancestors before descendants. Postorder: root last, descendants before ancestors.
Left-subtree node before right-subtree node (below their common ancestor) in all three orders. Leaf order is the same in all.
BST inorder is sorted. Expression tree: prefix, infix (brackets lost), postfix.
Mirror preorder $=$ reverse postorder.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 12.1 What is a binary search tree? (the inorder tree walk is defined in the text; from memory, the preorder and postorder walks appear in Exercise 12.1-4)
·Kernighan and Ritchie, The C Programming Language, 2nd ed., Section 6.5 Self-referential Structures (a recursive in-order print of a tree)

Verification

The four animations replay real runs of C functions on a real tree: the tree is drawn from the program's left and right pointers, the call stack and the queue are read from the running program, and the printed output is what the shown printf calls produce. The test suite checks the printed orders, that every traversal makes 7 calls on nodes and 8 calls on NULL for 7 nodes, and that the stack depth never exceeds the height plus one. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (leak detection off; the examples build small trees and do not free them). The claim about nodes in different subtrees of their lowest common ancestor was checked on every pair of nodes of every binary tree shape up to 8 nodes by a one-off script that is not part of the repository. The textbook section numbers were written from memory and have NOT been checked against the books. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Trees and binary trees

Constructing a tree from its traversals