Not an answer, but following the idea of Bullet and using the odd integers for $A$ instead gives the state diagram below for $k=2$ which (it seems) can be used to find $\Delta^{(k)}_{i}$.
As in Bullet's answer the directions at each level are given by $S_{n}$, the $n$-th digit from the right in the quaternary expansion of $i$, and when the digit $S_n$ does not appear in any of the outward pointing arrows from a vertex one terminates at the present node.
Edit: It has been pointed out by @მამუკაჯიბლაძე the earlier diagram had problems as early as $i=27$. After attempting to fix these problems, a new diagram was made which also had a minor problem (see comments). This is the latest diagram (but remains unchecked for large $i$). Here are the first 320 values in groups of $16$:
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8