Foundations — Level-order traversal — BFS with queue

Before you can read the parent note without stumbling, you must own every word and picture it leans on. Below, each idea is built from nothing, drawn, and justified — in an order where each one rests on the one before it.

1. A node — the atom of everything

Everything we build is made of nodes wired together. The parent note draws them as circles with numbers (1, 2, 3…). That number is just the node's value — its label so we can talk about it.

2. Parent, child, root, leaf — the family words

Nodes are connected by edges (the lines between circles). One node sits above and points down to others.

Why the topic needs these words: the whole algorithm is "start at the root, then visit each parent's children." Without root/parent/child you cannot even state the goal.

3. Level (depth) — the floors of the building

$\text{level}(\text{root})=0,\text{level}(\text{child})=\text{level}(\text{parent})+1$

That formula just says "one floor lower than my parent." Look at the figure: every node on the same horizontal row shares a level number.

Why the topic needs this: "level-order" literally means in order of increasing level. Also, on a tree the level of a node is exactly its distance from the root — that's the bridge to Breadth-First Search (BFS) and Shortest path in unweighted graphs, which think in terms of distance.

4. Width and height — the two ways a tree can be big

• A long thin skewed tree (each node has one child): tall height, width $1$.
• A complete tree (every level full): the bottom level alone holds about half of all nodes, so width $\approx n/2$.

Why the topic needs this: the parent note's space cost is $O(w)$, not $O(h)$. The queue at any instant holds roughly one level's worth of nodes, so its size tracks width. Knowing width vs height lets you predict when BFS is cheap (thin trees) or expensive (wide trees). See Tree height vs width.

5. node.left and node.right — reaching the children

Why the topic needs this: the BFS loop says if node.left: enqueue(node.left). That guard if node.left means "only if a left child actually exists." Skipping the guard and touching None.left is the parent note's Mistake C — a crash. See Binary Tree representation for how these two links define a binary tree.

6. FIFO and the queue — the polite waiting line

This is the heart of the topic, so we build it slowly and picture it.

Why a queue and not a stack? A stack is LIFO — Last In, First Out — like a pile of plates: you take the newest one off the top. If we used a stack, the most recently discovered (deepest) node would be served first, giving depth-first order. The queue serves the oldest discovered node, which is always closer to the root — that is exactly what keeps the sweep going floor by floor. Compare Queue (FIFO) data structure with Stack (LIFO).

7. Big-O notation — measuring cost without a stopwatch

Two symbols recur in the parent note:

Why the topic needs this: the parent claims time $O(n)$ (each node touched a constant number of times) and space $O(w)$ (the queue holds about one level). Big-O is the language that lets us reason about cost instead of memorizing it.

How these foundations feed the topic

Read it top-down: nodes give you family words, family words give you levels, levels are distances (the BFS idea), and the queue is the engine that visits them in that order. Big-O is the ruler you measure the result with.

Equipment checklist

Connections

• यही टॉपिक Hinglish में
• Queue (FIFO) data structure — the engine of this traversal.
• Stack (LIFO) — the LIFO contrast that would give DFS instead.
• Binary Tree representation — where .left / .right come from.
• Tree height vs width — why space is $O(w)$, not $O(h)$.
• Breadth-First Search (BFS) · Depth-First Search (DFS) · Shortest path in unweighted graphs