>would I have to make "doubly linked" nodes because the tree traversals eventually have to backtrack
No, but you do need to store the backtracking data somehow. Another option is to save the nodes in a stack.