Level-order traversal using a queue

0 · Recall Warm-up

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

• Postorder of a tree always ends with which node? from Lesson 4.3.1
• What is the minimum height of a binary tree with n nodes? from Lesson 4.2.2
• What does FIFO mean, and which structure follows it? from Lesson 3.3.1

1 · The Hook

🎣

A fire drill empties a building floor by floor, starting at the top. A news story spreads from the source to their friends, then to friends of friends. Both process things in “waves” by distance from the start. In a tree, that is level order: all nodes at depth 0, then depth 1, then depth 2.

2 · Predict First

🤔

Which structure should hold the nodes waiting to be printed, so that level-order comes out: a stack or a queue? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A queue. Children of the current level are discovered first and must be printed before their own children, which are discovered later: first discovered, first printed.

The algorithm

• Enqueue the root.
• While the queue is not empty: dequeue a node, print it, enqueue its left child and then its right child (if they exist).

void levelOrder(struct tnode *root)
{
    struct tnode *q[100];
    int front = 0, rear = 0;            /* simple array queue: q[front..rear-1] */
    if (root == NULL) return;
    q[rear++] = root;
    while (front < rear) {
        struct tnode *t = q[front++];   /* dequeue */
        printf("%d ", t->data);
        if (t->left)  q[rear++] = t->left;   /* enqueue children */
        if (t->right) q[rear++] = t->right;
    }
    printf("\n");
}

int main(void)
{
    levelOrder(mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL))));
    return 0;
}

Output

1 2 3 4 5 6 7

Each node is enqueued and dequeued once: O(n) time; the queue holds at most one level plus part of the next, up to about n/2 nodes for a complete tree.

Why not recursion?

The recursive traversals of Lesson 4.3.1 go deep along one branch before returning: the call stack is LIFO. Level order needs FIFO, so it is written with an explicit queue instead of recursion.

Variations

• Levels on separate lines: record the queue size at the start of each level and dequeue exactly that many.
• Height: count the number of levels − 1.
• Right to left: enqueue the right child first.
• For a tree stored in a 0-based array with no holes, level order is simply index order 0, 1, 2, … .

4 · Visual

Level-order trace on the example tree (computed).

Level-order positions on the example tree.

levels of the example tree:
 depth 0:  1
 depth 1:  2 3
 depth 2:  4 5 6
 depth 3:  7

queue snapshots:  [1] -> [2 3] -> [3 4 5] -> [4 5 6] -> [5 6] -> [6 7] -> [7] -> []

The queue always holds the frontier: the rest of one level and the start of the next.

5 · Worked Examples

Example 1 Easy

Level order of the Example 1 tree from Lesson 4.3.1 (A at the root)?

Solution

A B C D E F G H I.

Example 2 Medium

During level order of a perfect binary tree of height 3, what is the largest number of nodes in the queue at one time?

Solution

When the last node of level 2 is dequeued, the queue holds all of level 3: 8 nodes (just before that, 7 nodes of level 3 plus... at most 8).

Example 3 GATE

Write the nodes of the example tree level by level, and give the tree height from the number of levels.

Solution

depth 0: 1; depth 1: 2 3; depth 2: 4 5 6; depth 3: 7. 4 levels → height 3 (edges).

6 · GATE Traps

⚠️

• Level order uses a queue, not a stack (a stack would give a branch-first order).
• Enqueue the left child before the right child for left-to-right order.
• Level order is not any of pre/in/postorder.
• For a 0-based array without holes, level order is the index order.
• Number of levels = height + 1 (edges convention).

8 · Memory Hook

🧠

“Floor-by-floor fire drill: the queue is the stairwell.”

9 · Connect the Dots

Lessons 4.3.1–4.3.2 produced sequences from a tree. GATE often runs this backwards: given two of the sequences, draw the tree, or count how many trees fit. Next lesson answers: which pairs of traversals pin down a binary tree exactly, and how many different binary trees with n nodes exist?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markStructure

Level-order traversal is implemented with:

• (A) a queue
• (B) recursion only
• (C) a stack
• (D) sorting

Q2MCQ2 marksOutput

What does this print?

void levelOrder(struct tnode *root)
{
    struct tnode *q[100];
    int front = 0, rear = 0;            /* simple array queue: q[front..rear-1] */
    if (root == NULL) return;
    q[rear++] = root;
    while (front < rear) {
        struct tnode *t = q[front++];   /* dequeue */
        printf("%d ", t->data);
        if (t->left)  q[rear++] = t->left;   /* enqueue children */
        if (t->right) q[rear++] = t->right;
    }
    printf("\n");
}

int main(void)
{
    levelOrder(mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL))));
    return 0;
}

• (A) 1 3 2 6 5 4 7
• (B) 4 2 7 5 1 3 6
• (C) 1 2 3 4 5 6 7
• (D) 1 2 4 5 7 3 6

Q3NAT1 markLevels

A binary tree’s level-order traversal shows 5 distinct levels. What is its height (edges)?

Numerical answer: ________

Q4MCQ1 markArray

For a complete binary tree stored in a 0-based array, level order equals:

• (A) no simple order
• (B) inorder
• (C) reverse index order
• (D) index order 0, 1, 2, …

Q5MSQ2 marksFacts

Which are true about level-order traversal?

• (A) It uses the call stack for its order.
• (B) It visits each node once.
• (C) It can compute the height.
• (D) The first node printed is the root.

11 · Rule Card

• Level order: enqueue root; repeat: dequeue, print, enqueue left then right.
• O(n) time; queue holds at most about one level (≤ n/2 for complete trees).
• Stack → branch-first; queue → level order.
• Separate levels by recording the queue size; height = levels − 1.
• Array without holes: level order = index order.

12 · Concept Ledger

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

level-order traversalbreadth by levels (queue-based)frontier

13 · Answer Vault