Generate Binary Numbers
FIFO queue as a number factory
A queue is first-in-first-out: items leave in the exact order they arrived. Here that ordering IS the algorithm — dequeue the smallest binary string, output it, and enqueue its two children (append 0, then append 1). Because every parent enters the queue before its children, numbers leave in perfect ascending order with zero sorting.
Details
Animated on: Generate the binary representations of 1..5 in order using a queue: ["1", "10", "11", "100", "101"].
FIFO queue as a number factory
step 1 / 10
Seed the queue with "1" — every positive binary number starts with a 1 bit. We draw the queue as an array with a moving front pointer: dequeue = advance front, enqueue = append at the back.
- front=0· arr[0] = 1
- back=0· arr[0] = 1
1FUNCTION firstNBinary(n):2 queue = ["1"], out = []3 WHILE the length of out < n:4 s = remove the front of the queue (FIFO: oldest out first)5 append s to out (the next binary number)6 add s + "0" to the back of the queue (children join the back)7 add s + "1" to the back of the queue8 END WHILE9 RETURN out10END FUNCTION
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- Seed the queue with "1" — every positive binary number starts with a 1 bit. We draw the queue as an array with a moving front pointer: dequeue = advance front, enqueue = append at the back.
- out.length = 0 < 5, so loop. Dequeue the front — "1", the OLDEST item. It becomes output #1: binary 1 = decimal 1.
- Enqueue "1"+"0" = "10" and "1"+"1" = "11" at the BACK. Appending a bit to binary k gives 2k and 2k+1, so the children of 1 are 2 and 3 — and they join the line in that order.
- Front is now "10" — the older of the two waiting items. Dequeue it: output #2, binary 10 = decimal 2. FIFO is what guarantees 2 exits before 3.
- Enqueue "100" (decimal 4) and "101" (decimal 5) behind "11". The waiting queue now reads 3, 4, 5 front-to-back — still ascending, because smaller numbers were enqueued earlier.
- Dequeue "11": output #3, binary 11 = decimal 3. This is the FIFO payoff — "11" entered the queue before "100", so 3 leaves before 4. A stack (LIFO) would have emitted 4 first and scrambled the order.
- Enqueue "110" (6) and "111" (7). Waiting queue front-to-back: 100, 101, 110, 111 — exactly 4, 5, 6, 7. Every dequeue-then-append round keeps the whole line sorted.
- Dequeue "100": output #4 (decimal 4), and its children "1000" (8) and "1001" (9) join the back. The pattern in one line: dequeue number k, enqueue 2k and 2k+1.
- Dequeue "101": output #5 (decimal 5). Its children "1010" (10) and "1011" (11) still get enqueued before the loop re-checks — and now out.length = 5, so the while condition fails.
- Return out = ["1", "10", "11", "100", "101"] — the binary of 1..5, in order. The unused queue (grey) still reads 110, 111, 1000, 1001, 1010, 1011 = 6..11: FIFO kept every FUTURE number lined up in ascending order too.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.