Are non-deterministic tree-walking automata stronger than deterministic ones?
For tree automata, you have the following results:


Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata. 
Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.


More details can be found in the Tree Automata book.

It seems that you are interested in top-down tree automata, so the answer to your question is no. You will of course have to check whether top-down tree automata are in fact what you are interested in.