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

[![enter image description here][1]][1]

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 the earlier diagram had problems as early as $i=27$. After attempting to fix the problems with the diagram a new diagram above was made (but remains unchecked for large $i$).


  [1]: https://i.sstatic.net/0iVZg.png