iefpw
iefpw

Reputation: 7062

Fastest tree traversal

I have a pretty large tree data structure that will get updated (nodes removed and added, etc). I have to traverse the tree using breadth first approach to visit all the nodes (to a certain breadth depth like 7) and put it a to a list. Then a function will loop through the nodes and return true if an information was found inside of the list.

This is taking a lot of time to loop through the nodes. I don't think I should map every single node with every single children node and then pull the node using Dictionary and get all its children (recursively). How should I do this? The fastest way is to map all nodes between each other like

Dictionary<Node, List<Node>>

What is the best way to handle this situation? Any idea, pointers, comments, any thing is helpful. Currently this operation takes about 25% of the program run time.

Upvotes: 1

Views: 5877

Answers (1)

BrokenGlass
BrokenGlass

Reputation: 161002

If you are just evaluating a predicate you can do that directly while traversing the tree, you don't have to put the full tree into a list first - unless you cache the list. Evaluating the predicate on the the tree nodes directly, you can short circuit / stop traversing early when you first find the information you are interested in.

Upvotes: 2

Related Questions