Algorithm to recursivly go through a forest of children

Question

Hey! Please let me know if this is bad practice or in someway a bad thing to do. The thing is in my program I need to make a method which goes through the root element and all child nodes of that element. My elements are like this:

|--ID--|--Parent--|--Additinal info--|
|  1   |    0     | root element     |
|  2   |    0     | root elemnet     |
|  3   |    1     |child element of 1|
|  4   |    1     |child element of 1|
|  5   |    3     |child element of 3|
--------------------------------------

Now If I want to recieve all children of element with ID 1 (no matter if it has 1000 children or just 2 like in this example) I want my method to bring this too me, but Im not sure how to do it? All of these elements are in a List, and this is what Im working with. For each time I find an element I need to check if it has any children, the same goes with the children. This is because I need to output the elements in correct order. Ive been thinking of maybe make it so I first make a map of the layout, and then use the map for outputting, but Im kinda stuck with the idea.

Any clues?

Answer 1

It sounds like a graph traversal problem, so I would transform this list to a graph structure (using adjacency lists) and then traverse it with either DFS or BFS.

Answer 2

Your approach for representing hierarchical data is very inefficient when it comes to traversing the children of a node. You basically need to issue one query per node.

I highly recommend having a look at the nested set model (explained in this page). If you use this approach, you can traverse the children of a node using one query, regardless of the depth of the tree or the number of children.

Answer 3

Like a lot of these tree problems, the magic word here is recursion. The order you describe in the table is the order by IDs, which doesn't quite match depth or breadth first. But that's all right, all you need is to put the nodes into some data strcuture that will give them back in the order you want. So the general plan is

• recursively 'walk' the tree to find all the nodes; insert the nodes into a data strcuture that orders them by ID
• print the ordered nodes

The recursive part is also easy:

• start with the root node

• if the root node isn't in the list of nodes, add it

• take the first child node and do the same thing.

So something like (pseudocode):

dfs(node, nodelist):
   if node not in nodelist
      insert node in nodelist
   for each child node n
      dfs(n, nodelist)

Answer 4

You have to implement something like , looping in the list and for each of the current element of the list, finding the number of children, such as the number of elements in the list where element.Parent = currentElementofList.Id .If this element children count number is more than zero you have to get this children elements, and this continues until there are no more elements to be looped in the list.

Answer 5

What you need is the adjacency list model.

Check the article for details, but this method allows you to retrieve your tree with one query and the result is easy to walk through with your code. It's the fastest method for random tree access.