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 the problems with the diagram a new diagram was made which had a minor problem. This is the latest diagram (but remains unchecked for large $i$).