c++ - Tree Traversal: From Leaf to leaf and then up to the root

Question

Even though I am programming for quite some time I have to admit that I am struggling to come up with an algorithm that traverses a tree from leaf to leaf and then up, like this (the direction in which the inner nodes are traversed doesn't actually matter, 4 and 5 can be switched if necessary):

My setup at the moment looks like this (this is not a necessary a binary tree even though my drawing might suggest that):

struct Node {
    void *data;
    std::vector<Node*> next;
    std::vector<Node*> prev;
};

struct Tree {
    Node *root;
    
    TreeIterator begin() {
        
        /* Start at the very left leaf */
        Node *left_leaf = root;
        
        while( !left_leaf->next.empty() ) {
            left_leaf = left_leaf->next.first();
        }
        
        return TreeIterator(left_leaf);
    }
    
    TreeIterator end() { return TreeIterator(root); }
};

struct TreeIterator {
    
    TreeIterator(Node *_node) : node(_node) { }
    
    Node* operator*() const { return node; }
    void* operator->() const { return node->data; }
    
    TreeIterator& operator++() const {
        /* TODO: Jump to the next leaf and / or upwards */
        return *this;
    }
    
private:
    Node *node;
};

Do you might consider to give me some hints?

question from:https://stackoverflow.com/questions/65873185/tree-traversal-from-leaf-to-leaf-and-then-up-to-the-root

Answer 1

1. Make a BFS
2. Each node you take out of the queue you push_back into a vector.
3. Traverse the vector in reverse order.

Basically something like this:

queue<Node> q;
vector<Node> answer;
q.push(root);
while(!q.empty())
{
    Node first = q.front();
    answer.push_back(first);
    q.pop();
    for(every NODE reachable from first)
        q.push(NODE);
}
reverse(begin(answer), end(answer));

This is just the algorithm, I've put the closest to code that I could. You can make your iterator logic using vector answer now.

You could use a stack instead. The main point is: by traversing in a BFS you are doing the reverse sequence of what you are trying to achieve.