Build tree from flat JSON array in c++

Question

Essentially I have a JSON structure like this:

[
    {
        "id": "foo",
        "parent_id": null,
        "value": "This is a root node"
    },
    {
        "id": "bar",
        "parent_id": "foo",
        "value": "This is 2nd level node"
    },
    {
        "id": "baz",
        "parent_id": "bar",
        "value": "This is a 3rd level node"
    },
    {
        "id": "moo",
        "parent_id": "foo",
        "value": "This is another 2nd level node"
    },
    {
        "id": "woo",
        "parent_id": null,
        "value": "This is another root node"
    }
]

(Note that there's no ordering going on).

Now I would like to take that and parse it into a tree structure. Something like this (except using C++ types, not JSON):

[
    {
        "id": "foo",
        "value": "This is a root node",
        "children": [
            {
                "id": "bar",
                "value": "This is 2nd level node",
                "children": [
                    {
                        "id": "baz",
                        "value": "This is a 3rd level node",
                        "children": []
                    }
                ]
            },
            {
                "id": "moo",
                "value": "This is 2nd level node"
                "children": []
            }
        ]
    },
    {
        "id": "woo",
        "value": "This is another root node"
        "children": []
    }
]

I would imagine that it would look something like this, in pseudo-code, but I don't know enough C++ to actually make it work (I'm in the middle of a hack week. I have no idea what I'm doing :) )

struct NodeValue {
    std::string id;
    std::string value;
    std::string parent_id;
}

struct Node {
    NodeValue value;
    Node parent;
    std::deque<Node> children;
}

std::deque<Node> buildTree(json::Value nodes) {
    std::unordered_map<std::string, Node> lookup;

    // Populate our lookup map with all the nodes
    for (unsigned int i = 0; i < nodes.size(); ++i) {
        lookup.insert(std::make_pair(nodes[i].id, Node {
            NodeValue {
               nodes[i]["id"].asString(),
               nodes[i]["value"].asString(),
               nodes[i]["parent_id"].asString()
            },
            nodes[i]["id"].asString()
        }));
    }

    // Populate children
    for (lookup::iterator i = lookup.begin(); i != lookup.end(); ++i) {
        Node parent;
        try {
            parent = lookup.at(lookup[i].value.parent_id);
            parent.children.emplace_back(lookup[i]);
        } catch (out_of_range &e) {
            continue;
        }
    }

    // Remove all non-root nodes
    it = lookup.begin();
    while ((it = std::find_if(it, lookup.end(), [] (const Node& n) { return n.parent_id != NULL; })) != lookup.end()) {
        lookup.erase(it++);
    }

    return lookup;
}

I don't think this solution would work, unless the nodes are pre-sorted according to their depth level? Also, I literally wrote my first line of C++ two days ago, so have mercy.

Could anyone help me out?

Answer 1

Use a method on the Node struct along with a special "root node" collector:

struct Node {
    NodeValue value;
    Node* parent;
    std::deque<Node> children;
    void populateChildren(std::deque<Node>& source) {
        while (source.size() > 0) {
            std::deque<Node>::iterator child = std::find_if(
                source.begin(), source.end(), [this](Node possibleChild) {
                    return possibleChild.value.parent_id == this->value.id;
                }
            );
            if (source.end() == child) {
                return;
            }
            child->populateChildren(source);
            child->parent = this;
            children.push_back(*child);
            source.erase(child);
        }
    }
};

Then your rootNode has an id of null. It's children are then the top-level nodes whose parent_id will match null.

Then just do:

rootNode.populateChildren(setOfAllNodes);

I think that should work but I haven't tested it.

EDIT: Got it :). Below is a full working example (on GCC). The basic idea is the same as above but I had to switch to pointers because obviously I was deleting the underlying object with erase.

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

struct NodeValue{
    std::string id;
    std::string name;
    std::string parent_id;
};

struct Node {
    NodeValue value;
    Node* parent;
    std::deque<Node*> children;
    void populateChildren( std::deque<Node*>& source ) {
        auto child = std::find_if( source.begin(), source.end(), [this](const Node* const node){
            return node->value.parent_id == this->value.id;} );
        while ( child != source.end() ){
            (*child)->populateChildren( source );
            (*child)->parent = this;
            children.push_back( *child );
            source.erase( child );
            child = std::find_if( source.begin(), source.end(), [this](const Node* node){
                return node->value.parent_id == this->value.id;
            } );
        }
    }
};


void printChildCount( const Node* node ){
    std::cout << "Node " << node->value.name << " has parent "
            << ( ( node->parent == NULL ) ? "null" : node->parent->value.name ) << " and children: "
            << getListString(node->children) << std::endl;
    std::for_each( node->children.begin(), node->children.end(), printChildCount );
}

int main(){
    std::deque<Node*> nodes;
    Node node1{ NodeValue{ "1", "1", "root" }, NULL, std::deque<Node*>{} };
    Node node2{ NodeValue{ "2", "2", "root" }, NULL, std::deque<Node*>{} };
    Node node3{ NodeValue{ "3", "3", "1" }, NULL, std::deque<Node*>{} };
    Node node4{ NodeValue{ "4", "4", "2" }, NULL, std::deque<Node*>{} };
    Node node5{ NodeValue{ "5", "5", "2" }, NULL, std::deque<Node*>{} };
    Node node6{ NodeValue{ "6", "6", "5" }, NULL, std::deque<Node*>{} };
    Node node7{ NodeValue{ "7", "7", "5" }, NULL, std::deque<Node*>{} };
    Node node8{ NodeValue{ "8", "8", "7" }, NULL, std::deque<Node*>{} };
    nodes.push_back(&node5);
    nodes.push_back(&node6);
    nodes.push_back(&node3);
    nodes.push_back(&node8);
    nodes.push_back(&node4);
    nodes.push_back(&node7);
    nodes.push_back(&node1);
    nodes.push_back(&node2);
    Node rootNode { NodeValue { "root", "root", "" }, NULL, std::deque<Node*> { } };
    rootNode.populateChildren( nodes );
    printChildCount( &rootNode );
    return 0;
}