Visiting Every Node: Traversals

Four orders

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int value;
    Node *left, *right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
};

void preorder(Node* n)  { if (!n) return; cout << n->value << ' '; preorder(n->left); preorder(n->right); }
void inorder(Node* n)   { if (!n) return; inorder(n->left); cout << n->value << ' '; inorder(n->right); }
void postorder(Node* n) { if (!n) return; postorder(n->left); postorder(n->right); cout << n->value << ' '; }

int main() {
    Node* root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    cout << "pre:  "; preorder(root); cout << endl;
    cout << "in:   "; inorder(root); cout << endl;
    cout << "post: "; postorder(root); cout << endl;

    cout << "levels:" << endl;               // level order with a queue (BFS)
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();                  // everything in the queue now is one row
        for (int i = 0; i < size; i++) {
            Node* n = q.front();
            q.pop();
            cout << n->value << ' ';
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        cout << endl;
    }
    return 0;
}

Output

pre:  1 2 4 5 3 
in:   4 2 5 1 3 
post: 4 5 2 3 1 
levels:
1 
2 3 
4 5 

Think of it like this: Preorder is like a table of contents: chapter title first, then its sections. Postorder is like deleting a folder: everything inside must go first.