The algorithm to generate binary numbers from 1 to n in lexicographical order

The key property here is, 0 will always come before 1, so you can use recursion to solve this. The algorithm would look like:

1. Start recursion from 1
2. If current number > n, ignore it
3. Else, add it to the output list. Call recursion(curr_number + "0") and recursion(curr_number + "1")

This is a simple algorithm, which can be easily implemented in most languages.

Edit: Python implementation:

def dfs(current_string, current_number, n):
    if current_number > n:
        return []
    strings = [current_string]
    strings.extend(dfs(current_string + "0", current_number << 1, n))
    strings.extend(dfs(current_string + "1", (current_number << 1)+1, n))
    return strings
print(dfs("1", 1, 7))

If you number a complete binary tree row by row, from 1 to 2^d-1, the enumeration of the nodes in lexicographical order is the preorder traversal. Now as the two children of a node carry the value of the parent followed by 0 or by 1, we have the recursive enumeration

n= ...

def Emit(m):
    print(bin(m))
    if 2 * m <= n:
        Emit(2 * m)
    if 2 * m + 1 <= n:
        Emit(2 * m + 1)

Emit(1)

(You can also obtain the binary representations by concatenating 0's or 1's as you go.)

There are a few rules you can follow to generate the next item in a lexicographical ordering of any set of strings:

1. The first symbol that changes must increase (otherwise you'll get an earlier symbol)
2. The first symbols that changes must be as far right as possible (otherwise there would be a smaller lexicographical change); and
3. The symbols after the first change must be made as small as possible (otherwise again there would be a smaller lexicographical change).

For ordering the binary strings, these rules are easy to apply. In each iteration:

1. If you can append a zero without exceeding n, then do so;
2. Otherwise, find the rightmost possible 0, change it to a 1, and remove the remainder. The "rightmost possible 0" in this case is rightmost one that produces a result <= n. This is not necessarily the rightmost one if n is not 2^x-1.

This iteration is pretty easy to implement with bitwise operators, leading to this nice quick algorithm. To simplify step (2), we assume that n is 2^x-1 and just check our outputs:

def printLexTo(n):
    val=1
    while True:
        if val<=n:
            print("{0:b}".format(val))
        if 2*val <= n:
            val *= 2
        else:
            # get the smallest 0 bit
            bit = (val+1) & ~val
            # set it to 1 and remove the remainder
            val = (val+1)//bit
            if val==1:
                # there weren't any 0 bits in the string
                break

Try it online

As is often the case, this iterative algorithm is a lot faster than recursive ones, but coming up with it requires a deeper understanding of the structure of the solution.