We study the existence, optimality, and construction of non-randomised stopping times that solve the Skorokhod embedding problem (SEP) for Markov processes which satisfy a duality assumption. These stopping times are hitting times of space-time subsets, so-called Root barriers. Our main result is, besides the existence and optimality, a potential-theoretic characterisation of this Root barrier as a free boundary. If the generator of the Markov process is sufficiently regular, this reduces to an obstacle PDE that has the Root barrier as free boundary and thereby generalises previous results from one-dimensional diffusions to Markov processes. However, our characterisation always applies and allows, at least in principle, to compute the Root barrier by dynamic programming, even when the well-posedness of the informally associated obstacle PDE is not clear. Finally, we demonstrate the flexibility of our method by replacing time by an additive functional in Root's construction. Already for multi-dimensional Brownian motion this leads to new class of constructive solutions of (SEP).