Magyar has shown that if B ⊂ ℤd has positive upper density (d ⩾ 5), then the set of squared distances {||b1 − b2||2 : b1, b2 ∈ B} contains an infinitely long arithmetic progression, whose period depends only on the upper density of B. We extend this result by showing that B contains locally isometrically embedded copies of every tree with edge lengths in some given arithmetic progression (whose period depends only on the upper density of B and the number of vertices of the sought tree). In particular, B contains all chains of elements with gaps in some given arithmetic progression (which depends on the length of the sought chain). This is a discrete analogue of a result obtained recently by Bennett, Iosevich and Taylor on chains with prescribed gaps in sets of large Haussdorf dimension. Our techniques are Ergodic theoretic and may be of independent interest to Ergodic theorists. In particular, we obtain Ergodic theoretic analogues of recent optimal spherical distribution results of Lyall and Magyar which, via Furstenberg's correspondence principle, recover their combinatorial results.