Traversing a general tree structure starting from an arbitrary node in C#

Question

I need tree traversal algorithms for arbitrary trees in both Depth-first and Breadth-first Traversal order. The tricky part is that I need to be able to start from an arbitrary node and continue until another specific node is traversed.

Now, I can use any of the ordinary algorithms and ignore the traversed nodes until I hit the start node and continue until the end node (which I currently do) but this is ugly and inefficient.

Any suggestions, please.

UPDATE: Each of my nodes have an id associated with them. In some cases, I have start and end node references to start with. In other cases, I am given two Ids, I check whether the given node is the start node or the end node by inspecting their ids. I use depth-first traversal to find the start node. Both the start and end nodes can be anywhere in the hierarchy. I hope someone could come up with an idea for the case where I am already given references to both the start-node and end-node. BTW, the nodes in the tree is actually sorted according to a sort order, which starts from 0 for each of the sub-nodes of a node and there is one root node

Answer 1

I think what you are doing is the most efficient way to do. Especially if you are working with arbitrary trees.

You are given an arbitrary tree and you need to find the node to start the traversal from. Since there is no hierarchy (ie: it s not binary tree) you will have to scan the nodes (you might end up scanning more than half the nodes if the given node is a leaf node or if the node is not in the tree you will have to search the whole tree) until you find the node to start with. Once you find the node, you can start your DF Traversal or BF Traversal.

I dont see any optimization you can do.