Take the 2-minute tour ×

I've been searching for a while now and can't seem to find an alternative solution. I need the tree traversal algorithm in such a way that a node can have more than 1 parent, if it's possible (found a great article here: Storing Hierarchical Data in a Database). Are there any algorithms so that, starting from a root node, we can determine the sequence and dependencies of nodes (currently reading topological sorting)?

share|improve this question
a vote down... just wish they'd leave a comment, so we can improve..... –  poldo Apr 21 '10 at 10:17
Will you store the data in the database? If not disregard the above article, it is specific to 'hierarchical data in relational database' problem. –  Unreason Apr 21 '10 at 10:24
btw +1 for an unexplained/undeserved downvote. –  sfussenegger Apr 21 '10 at 10:27

4 Answers 4

up vote 1 down vote accepted

A tree is basically a directed unweighted graph, where each vertice has N or less edges, and no cycles can happen.
If your'e certain there are no cycles in your tree, you could just treat a parent as another child of the specified node, and preform a preorder traversal normally.
However, if cycles might happen, you need graph algorithms.
Specifically: Breadth first search.

share|improve this answer
Thanks! implementing it should be easy enough, although I might go with the tree, since it needs to be retrieved quite frequently. :) –  poldo Apr 21 '10 at 10:05

The structure you described isn't a tree, it's a directed graph. As it would be suitable for hierarchical drawing you might be tempted to think of it as a tree (which itself is an acyclic connected graph).

Typical traversal algorithms for graphs are depth-first and breadth-first. The graph implementation is only different as it records the nodes it has already visited in order to avoid visiting certain nodes multiple times. However, if your data structure guarantees that it's acyclic, you can use tree algorithms on your graph by simply treating "parents" as "children".

I made a simple sketch to illustrate what I mean (the perfect chance to try Google Docs' new drawing feature): alt text

As you see, it's possible to treat any graph that has an acyclic directed form as a tree and apply tree algorithms on it. As soon as you can't guarantee this property you'll have to go for dedicated graph algorithms.

share|improve this answer
whoah... graph thery seems very daunting, will give it a shot. I'm checking out dependency algorithm too. thanks for the quick response! –  poldo Apr 21 '10 at 9:19
@poldo I think I've made myself clearer now –  sfussenegger Apr 21 '10 at 13:06
I am confused. In the orginal graph 1->3 , but in the traversal 3->1 how is this possible? –  mosaad Aug 14 at 7:48

Just checking for maybe a simple case: can the two parents have different parents? If no you could turn them into single node (conceptually) and have a tree again.

Otherwise you will have to split the child node and duplicate a branch for the other parent. (This can of course lead to inconsistency and/or inneficient algorithms later, depending if you will need to maintain the data structure).

The above options hold if you insist on having the tree structure, which by definition can have only one parent.

So maybe you need to step back and explain what are you trying to accomplish and why it must be a tree structure if nodes can have two parents.

share|improve this answer

You aren't describing a tree here. You can NOT call your graph a tree.

A tree is an undirected graph without cycles. Parent/child relationship is NOT an interpretation of directions drawn on the edges. They are the result of naming one vertex the root.

We name a vertex "parent" to current, because it's the next one to the path to root. All other vertexes adjacent to current one are "children".

You can't just lay out an arbitrary graph in such a way that "parents" are "above" or "point to vertex", and children are "below" or "vertex points to them". A tree is a tree because a root is picked. What you depict in your question is not a tree. And tree traversal algorithms are NOT applicable to traversing arbitrary graphs.

There are several graph traversal algorithms, such as breadth-first search or depth-first search (check side notes in those pages for more). Use them instead of trying to tie your full-featured graph into your knowledge about trees.

share|improve this answer

Your Answer


