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

Question

I need tree traversal algorithms for arbitrary trees in both first and first traversal order. The tricky part is that I need to start with an arbitrary node and continue until another specific node is passed.

Now I can use any of the usual algorithms and ignore the nodes passed until I’m at the beginning of the node and continue to the end of the node (which I am doing now), but this is ugly and inefficient.

Any suggestions please.

UPDATE: each of my nodes has an identifier associated with them. In some cases, I have the beginning and end of node links to start with. In other cases, they give me two identifiers, I check if a given node is the beginning of a node or the end of a node by checking their identifiers. I use depth traversal to find the beginning of a node. Both the start and end nodes can be anywhere in the hierarchy. I hope that someone can come up with an idea for the case when I have already been given links to the initial - node and end - node. BTW, the nodes in the tree are actually sorted according to the sort order, which starts at 0 for each of the sub-nodes of the node and there is one root node

Answer 1

I think what you are doing is the most effective way to do it. Especially if you work with arbitrary trees.

You are given an arbitrary tree, and you need to find the node to start the crawl. Since there is no hierarchy (i.e.: this is not a binary tree), you will have to scan the nodes (you can complete the scan for more than half of the nodes, if the given node is a leaf of the node or if the node is not in the tree, you will have to search all over the tree) while you you will not find node to start with. When you find node, you can start tracing DF or bypassing BF.

I do not see any optimization you can do.

Answer 2

Instead

Traverse(RootNode, StartNode, EndNode) 

Pass the start of the node as root

 Traverse(StartNode, EndNode) 

However, if you want to return nodes that are not children of your node run, you will have to continue using your current method.

Answer 3

If you have to answer many unrelated requests, and you need to specify the path (instead of just saying that it exists or not), then you can not do better than you have AFAIK now.

On the other hand, if you expect a large number of queries related to a small number of specific nodes (for example, what are the paths from A to B, C, D, E, F and G?), You can first calculate the minimum spanning tree from this node ( s) and make your BFS more efficient.