how to extract a tree iteration in C++

Question

I've been repeating a chunk of similar code for several times. This how it's like in pseudo code:

stack.push(root)
while stack size > 0
  node = stack.pop()
  if condition_1
    if node is leaf
      if condition_2
        // do something,
        // for example, push node into a vector and return the vector
    else
      stack.push(children of node)

or like this:

stack.push(root)
while stack size > 0
  node = stack.pop()
  if condition_1
    if node is leaf
      if condition_2 // or no condition_2 and return true directly
        return true
    else
      stack.push(children of node)
return false

The difference between this two snippets is that the first one iterates all leaf nodes, while the second one has a break logic. And usually the main work I do is condition_2 and what's in its scope. Other lines are just repeating themselves.

So is there a way to extract this kind of tree iterating loop, in C++ or any other language?

The visitor pattern can be used for this: [Visitor pattern where the visitors choose how to traverse](https://stackoverflow.com/questions/24565781/visitor-pattern-where-the-visitors-choose-how-to-traverse) — Thomas, Nov 22 '19 at 10:33

Valeriy Savchenko · Answer 1 · 2019-11-22T11:27:14.430

As I understood correctly, you want to have a generic version of this algorithm.

I don't know which parts you do want to make generic, so here is a very simple solution where everything is generic.

template <class NodeType, class TraversalPredicate, class LeafPredicate,
          class TerminalPredicate, class ChildrenGetter>
bool findIf(NodeType *root, TraversalPredicate shouldTraverse,
            LeafPredicate isLeaf, TerminalPredicate shouldFinish,
            ChildrenGetter getChildren) {
  std::stack<NodeType *> stack;
  stack.push(root);

  while (not stack.empty()) {
    auto *node = stack.top();
    stack.pop();
    if (not shouldTraverse(node))
      continue;

    if (isLeaf(node)) {
      if (shouldFinish(node)) {
        return true;
      }
    } else {
      for (auto *child : getChildren(node)) {
        stack.push(child);
      }
    }
  }
  return false;
}

I hope that is what you were looking for!

how to extract a tree iteration in C++

1 Answers1