CODEWITHSUNDEEP
.netalgorithmtree-traversal
Kemal Erdogan
Kemal Erdogan

Reputation: 1080

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

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

Upvotes: 6

Views: 1363

Answers (3)

Jon
Jon

Reputation: 437784

If you are going to have to answer lots of unrelated queries, and you need to provide a path (instead of just saying that one exists or not) then you can't do better than what you have now AFAIK.

On the other hand, if you expect lots of queries involving a small number of specific nodes (e.g. what are the paths from A to B, C, D, E, F, and G?) then you can first calculate the minimum spanning tree from that node(s) and make your BFS more efficient.

Upvotes: 0

DarthVader
DarthVader

Reputation: 55112

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.

Upvotes: 2

Louis Ricci
Louis Ricci

Reputation: 21106

Rather than

Traverse(RootNode, StartNode, EndNode)

Pass the start node as the root

Traverse(StartNode, EndNode)

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

Upvotes: 0

Related Questions