Fastest tree traversal

Question

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>>

• node, list of all children (including children of children...) and then pull the nodes and get its like 2,000 children fast. But if a node is added or removed anywhere, all the dictionary nodes need to be updated (which seems like a hassle). The other way is to dynamically loop through it during run (which takes time). It is a matter of mapping everything together in the beginning during tree generation, or looping during run time.

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.

Answer 1

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.