The state-space tree searched by parallel DFS can be efficiently represented as a stack.
Memory requirement of the stack is linear in depth of tree.
DFS Storage Requirements and Data Structures
Representing a DFS tree: (a) the DFS tree; Successor nodes shown with dashed lines have already been explored; (b) the stack storing untried alternatives only; and (c) the stack storing untried alternatives along with their parent. The shaded blocks represent the parent state and the block to the right represents successor states that have not been explored.