Pattern visualizer

Generate Binary Numbers

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. 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

time O(n)space O(n)step 1 / 10

[0]

line 2

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.

Pseudocode

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 queue
8  END WHILE
9  RETURN out
10END FUNCTION

← / → step · space play · Home restart

Where to practice Queue

Practice Queue problems All Queue problems Back to roadmap