Number of ways to traverse an N-ary tree

Preorder Recursive

To generalize the above to n-ary trees, you simply replace the steps:

Traverse the left subtree.... Traverse the right subtree...   (Binary Tree)

in the above by:

For each child:   (N-ary Tree)
  Traverse the subtree rooted at that child by recursively calling the traversal function

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        preorder(root, res);

        return res;
    }

private:
    void preorder(Node* root, vector<int> &res) {
        if (root == nullptr) return;
        res.push_back(root->val);

        for (auto node : root->children) {
            preorder(node, res);
        }
        return;
    }
};

Preorder Iterative

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        stack<Node*> st;
        if (root == nullptr) 
            return res;

        st.push(root);
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            res.push_back(node->val);

            for (int i = node->children.size() - 1; i >= 0; --i) {
                st.push(node->children[i]);
            }

        }
        return res;
    }
};

Postorder Recursive

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        postorder(root, res);

        return res;
    }

private:
    void postorder(Node* root, vector<int> &res) {
        if (root == nullptr) return;

        for (auto node : root->children) {
            postorder(node, res);
        }
        res.push_back(root->val);
        return;

    }
};

Postorder Iterative

// Method 1: res.insert(res.begin(), n->val);
class Solution {
public:
    vector<int> postorder(Node* root) {
        stack<Node*> s; s.push(root);
        vector<int> result;
        while (!s.empty() && root) {
            Node * n = s.top(); s.pop();
            result.insert(result.begin(), n->val);
            for (auto & ch : n->children) s.push(ch);
        }
        return result;
    }
};

Level order Iterative

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int> > res;
        queue<Node*> cur, next;

        if (root == nullptr) return res;

        cur.push(root);
        while (!cur.empty()) {
            vector<int> tmp;
            while (!cur.empty()) {
                Node* node = cur.front();
                cur.pop();
                tmp.push_back(node->val);
                for (auto & it : node->children) {
                    next.push(it);
                }
            }

            res.push_back(tmp);
            swap(cur, next);
        }

        return res;
    }
};

Wrong

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int> > res;
        queue<Node*> cur, next;

        if (root == nullptr) return res;

        cur.push(root);
        // bug
        while (!cur.empty()) {
            vector<int> tmp;
            Node* node = cur.front();
            cur.pop();
            tmp.push_back(node->val);

            for (auto & it : node->children) {
                next.push(it);
            }
            res.push_back(tmp);
            swap(cur, next);
        }

        return res;
    }
};

Wrong: [[1],[3],[5],[2],[6],[4]]
Output: [[1],[3,2,4],[5,6]]