Consider the following

o

/ o i

/

j

I is less deep than J, yet in a 'depth first' search, it may not necessarily come before J in a search.. Only in a BREADTH-FIRST search would I ALWAYS come before J.....

In a depth-first search their ordering is indeterminate unless i is one of j's ancestors.