Walking a tree, parent first

Question

What is the best way to visit all the nodes of a linked tree (all nodes have references to parent and all children, root nodes have null as parent), so that no node is visited before any of its ancestors? Brownie points for non-recursive.

Answer 1

Pseudo code:

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

Edit: Recursive or not?
To be technically correct, and as pointed out by AndreyT and others in this post, this approach is a form of a recursive algorithm, whereby an explicitly managed stack is used in lieu of the CPU stack and where the recursion takes place at the level of the While loop. This said, it differs from a recursive implementation per se in a couple of subtle yet significant ways:

• Only the "variables" are pushed onto the stack; there is no "stack frame" and associated return address on the stack, the only "return address" is implicit to the while loop, and there is but one instance of it.
• The "stack" could be used as a list whereby the next "frame" could be taken anywhere in the list, without braking the logic in any way.

Answer 2

Breadth First Search

Answer 3

You're looking for a preorder traversal. I think you can do it non-recursively with a queue:. In pseudocode:

Create an empty queue, then push the root node.

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)