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?

Collector

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

Triplicity

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

Caban

If it's not homework and he wants a DFS, definitely. He did specifically ask for a way of doing it with loops though. BFS is not done well with recursion either way. – Triplicity

Yea, this isn't homework, this is for an app I'm building and I'm trying to populate a list that, well is like a comments page so there are levels of replies. Main comment, reply, reply off of that reply, etc. So I was looking for a way to parse through the comments and build the appropriate HTML for the structure. – Collector

Answer 3

Just use recursion like

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

Fryer

Just a small tweak but it's usually a lot cleaner for the "do something" to be outside of that loop. This way misses the root node. – Triplicity

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.

Fiducial