Tree traversal algorithm

Question

Update:
I found more example of what I'm trying to accomplish: Managing hierarchical data in MySQL . I want to do this, but in JavaScript, because I am creating an application that accepts comments that are in a hierarchical structure, specifically reddit.com. If you have a Pretty JSON extension on your chrome web browser, go to reddit and click on the thread comments, and then add .json to the url to see what I'm parsing. I get JSON data just fine, just parsing the comments and adding the appropriate HTML to show that it is nested. Ideas for solutions?

---

Old question:
I am working on a program, and I have come to the conclusion that I need to figure out the logic before writing code. I take data that is in a tree format, but with the possibility of several children for each parent node, and the only tree on which I can find the data is a tree with weights or a tree where no more than two nodes have two child nodes. Therefore, I am trying to calculate an algorithm to evaluate each node tree as follows:

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

Now, when I try to write how my algorithm works, I end up writing nested / while loops, but in the end I am writing a loop for each level of tree height, which for dynamic data and a tree of unknown height with an unknown number of children per node is not working. I know that at some point I found out how to cross such a tree, but that completely eludes me right now. Does anyone know how this is done in terms of loops?

Answer 1

If you are not going to use recursion, you need an auxiliary data structure. A queue will give you a bypass of the width, while a stack will give you a bypass of the depth. In any case, it looks something 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 Links

• Queue
• Stack

Answer 2

Use recursion, not loops.
First width search
First Search Depth
This should help you get started with what you are trying to do.

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 walks is usually recursive. For a multi-track tree like yours, it is usually easiest to have a loop that looks at each pointer to a child element and calls itself node as an argument to all child nodes.