Is there a good way to print out a flattened namespace for a JSON-like trie structure (iterative solution only) in C++11?

Question

I'm attempting to create a trie structure in C++, where each node holds a name, and some data, and can hold references to children nodes of any number.

I'd like to traverse my trie such that I print out the "flattened" path to a given node in an iterative fashion.

Given some Tree where a node is defined by:

    class Node
    {
            public:
            virtual std::string node_name() = 0;
    };


    class TreeNode : Node
    {
    public:
        std::string name;
        std::map<std::string, TreeNode&> children {};


        TreeNode(const std::string&name) : name(name) {}


        std::string node_name()
        {
            return name;
        }

        void add_child(TreeNode& node)
        {
                children.insert(std::pair<std::string, TreeNode&> 
                (node.node_name(), node));
        }

    };

If I add children via:

    TreeNode root { "root" };

    TreeNode a { "a" };
    TreeNode b { "b" };

    TreeNode c { "c" };
    TreeNode d { "d" };
    TreeNode e { "e" };


    a.add_child(c);
    a.add_child(d);

    b.add_child(e);

    root.add_child(a);
    root.add_child(b);

    // flatten the tree and print out the namespace here
    flatten(root);

The output should be (don't care about order):

    root
    root.a
    root.a.c
    root.a.d
    root.b
    root.b.e

I've already implemented the recursive solution (see below), but I'd like to know if there's a way to do this iteratively (since I'd like to avoid recursion if possible in my application).

Here is the recursive version:

    void flatten_helper(TreeNode& root, 
                        const std::string& prefix)
    {
        static const std::string delimeter { "." };

        std::string namespace_path(prefix);
        if (!prefix.empty())
        {
            namespace_path.append(delimeter);
        }

        namespace_path.append(root.node_name());

        for (auto& node : root.children)
        {
            flatten_helper(node.second, namespace_path);
        }
        // do something with node/complete namespace name
        std::cout << namespace_path << std::endl;


    }

    void flatten(TreeNode& node)
    {
        std::string empty {""};

        return flatten_helper(node, empty);
    }



    int main(int argc, char** argv)
    {
        TreeNode root { "root" };

        TreeNode a { "a" };
        TreeNode b { "b" };

        TreeNode c { "c" };
        TreeNode d { "d" };
        TreeNode e { "e" };


        a.add_child(c);
        a.add_child(d);

        b.add_child(e);

        root.add_child(a);
        root.add_child(b);

        flatten(root);

        return 0;
    }

I'm a bit stumped on how to approach the iterative version in c++11 (have tried a few iterations of various tree traversals) - any help would be appreciated.

Answer 1

The trick to converting recursive processes into interative processes is to make the 'pending work' explicit. In your case, a unit of work is a TreeNode and a prefix, and the work units are kept in a std::stack (as your recursive solution is depth-first). Any (previously) recursive calls must add work to the stack, and work stops when no more work is available.

void flatten_iter(TreeNode& root_node)
{
    using WorkItem = std::pair<TreeNode&, std::string>;
    static const std::string delimeter{ "." };

    std::stack<WorkItem> workitems;
    workitems.emplace(root_node, "");

    while (!workitems.empty()) {
        auto [ node, prefix ] = workitems.top();
        workitems.pop();

        std::string namespace_path(prefix);
        if (!prefix.empty())
        {
            namespace_path.append(delimeter);
        }

        namespace_path.append(node.node_name());

        for (auto& child : node.children)
        {
            workitems.emplace(child.second, namespace_path);
        }

        // do something with node/complete namespace name
        std::cout << namespace_path << std::endl;
    }
}