Algorithm for Tree Traversal

Question

Update:
I found more of an example of what I'm trying to pull off: Managing Hierarchical Data in MySQL. I want to do that but in JavaScript because I am building an app that takes in comments that are in a hierarchical structure, to be more specific reddit.com. If you have the Pretty JSON extension on your chrome web browser go to reddit and click on a threads comments and then add .json to the url to see what I am parsing.
I get the JSON data just fine, its just parsing through the comments and adding the appropriate HTML to show that its nested.
Ideas for solutions?

---

OLD question:
I am working on a program and I have come to a part that I need to figure out the logic before I write the code. I am taking in data that is in a tree format but with the possibility of several children for each parent node and the only tree's I can seem to find data on are tree's with weights or tree's where at most each node has two child nodes. So I'm trying to figure out the algorithm to evaluate each node of a tree like this:

startingParent[15] // [# of children]
    child1[0]
    child2[5]
       child2ch1[4]
       ...
       child2ch5[7]
    child3[32]
    ...
    child15[4]

Now when I try to write out how my algorithm would work I end up writing nested for/while loops but I end up writing a loop for each level of the height of the tree which for dynamic data and tree's of unknown height with unknown number of children per node this doesn't work. I know that at some point I learned how to traverse a tree like this but its completely escaping me right now. Anyone know how this is done in terms of loops?

Answer 1

If you're not going to use recursion, you need an auxiliary data structure. A queue will give you a breadth-first traversal, whereas a stack will give you a depth-first traversal. Either way it looks roughly like this:

structure <- new stack (or queue)
push root onto structure
while structure is not empty
  node <- pop top off of structure
  visit(node)
  for each child of node
     push child onto structure
loop

Wikipedia References

• Queue
• Stack

Answer 2

Use recursion, not loops.
Breadth first search
Depth first search
Those should help you get started with what you're trying to accomplish

Answer 3

Just use recursion like

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)

Answer 4

The simplest code for most tree traversal is usually recursive. For a multiway tree like yours, it's usually easiest to have a loop that looks at each pointer to a child, and calls itself with that node as the argument, for all the child nodes.