Efficient way to walk through an object tree?

Question

I've got a set of TreeNodes, each of which has an id, a Collection of parent nodes, and a collection of child nodes.

For a given node Id, I'm looking for an efficient way to generate all the links that pass through that node. So in short, start at the node, and iterate through all its children. If a node has more than one child, create a link for each child. The traverse the children etc..

I'd also like to be able to do this in an 'upward' direction, through the parent nodes.

Is there a simple algorithm to do this?

EDIT: Oh, and I'd like to be able to output the id's of all the nodes in a given chain...

Answer 1

Well, if the nodes have a reference to the parent, it's simple as getting the parent recursively (once in a tree, each node has only one (or none at all, if it is a root) parent.

If there's no such reference, than you could use a breadth-first search, for instance, having as initial set your collection of parent nodes.

-- EDIT --

Once a node may have more than one parent, then you're dealing with a graph. There are also graph traversal algorithms (see table at the side).

Make sure that, if your graph has a cycle, you won't end up having a infinite loop

Answer 2

You are looking for a Breadth First or Depth First Search. At first it is not more than the following (this is depth first search).

Visit(Node node)
{
    foreach (Node childNode in node.Children)
    {
        Visit(childNode);
    }

    DoStuff(node);
}

The problem is that the graph may contain cycles, hence the algorithm will enter infinite loops. To get around this you must remember visited nodes by flaging them or storing them in a collection. If the graph has no cycles - for example if it is a tree - this short algorithm will already work.

And by the way, if a TreeNode has multiple parents, it's not a tree but a graph node.

Answer 3

This is a usecase of the visitor pattern

Greetz, GHad

Answer 4

You might want to check out depthFirstEnumeration() and breadthFirstEnumeration() on DefaultMutableTreeNode. However, this doesn't solve your problem of wanting to navigate the tree in a bottom-up fashion.