Let $\{0,1\}^{<\omega}$ be the collection of $x \in \{0,1\}^\omega$ such that there is $N\in\omega$ with $x(k) = 0$ for all $k\geq N$. We say that $ x, y\in \{0,1\}^{<\omega}$ form an edge if they have Hamilton distance $1$ (that is, there is a unique $k\in\omega$ such that $x(k) \neq y(k)$.


**Question.** Is there a bijection $p:\omega\to \{0,1\}^{<\omega}$ such that $p(k), p(k+1)$ form an edge for all $k\in\omega$?



Does $\{0,1\}^{<\omega}$ have a Hamiltonian path?
*I'm going to write $\mathcal{S}$ for what you call $\{0,1\}^{<\omega}$, since I'm used to the latter referring to the set of finite binary strings.*


Yes, and moreover there is a relatively simple process for building such a path. The key is the following lemma:



> 
> For any finite set $A\subseteq\mathcal{S}$ and any distinct $\alpha,\beta\in\mathcal{S}\setminus A$, we can find a path from $\alpha$ to $\beta$ in $\mathcal{S}$ which does not go through any point in $A$ and does not reuse points.
> 
> 
> 


Basically, we fix some $n\in\omega$ such that every $\gamma\in A$ has $\gamma(n)=0$, and additionally $\alpha(n)=\beta(n)=0$; then starting at $\alpha$, we first "flip the $n$th bit" of $\alpha$, then greedily change $\alpha$ to $\beta$, then "flip back" the $n$th bit.


Iterating this lemma lets us build a Hamiltonian path through $\mathcal{S}$ via a greedy algorithm: having already determined the first $k$ points $\pi\_1,...,\pi\_k$ of our Hamiltonian path, let $\alpha=\pi\_k$, let $A=\{\pi\_1,...,\pi\_{k-1}\}$, and let $\beta$ be the lex-least element of $\mathcal{S}\setminus (A\cup\{\alpha\})$.


