N-ary Tree Preorder Traversal

Problem

Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value.

Follow up: Recursive solution is trivial, could you do it iteratively?

Constraints

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

Solution

The problem N-ary Tree Preorder Traversal can be solved using a depth-first search by iteratively popping the stack and saving it’s child nodes back into the stack in reverse order.

Implementation

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

class Solution
{
  public:
    vector<int> preorder(Node *root)
    {
        vector<int> ret;
        if (root == NULL)
            return ret;

        stack<Node *> nodes;
        nodes.push(root);

        while (!nodes.empty())
        {
            root = nodes.top();
            nodes.pop();

            ret.push_back(root->val);
            for (auto rit = root->children.rbegin(); rit != root->children.rend(); rit++)
                nodes.push(*rit);
        }

        return ret;
    }
};