Efficient algorithm for hierarchical traversing? JSON hydration, for example

Question

I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example:

{
    "date": "1970-01-01 00:00:00",
    "foobar": "baz",
    "user": {
        "name": "foobar",
        "id": 2
    }
}

And the following library ruleset:

Hydrator hydrator = new Hydrator
hydrator.add("date", DateTime)
hydrator.add("foobar", String)
User user = hydrator.add("user", User)
user.add("name", String)
user.add("type", Integer)

DataSet data = hydrator.parse(jsonInput)

So far, it's working great. I have created a Node, and each Node can have children. I just walk through the entire JSON file, create Node instances for each key/value, and create the hierarchy. When i instance the node, i add some metadata. Then, in a big method, i walk through the entire node tree and hydrate depending on the metadata. However, i'm looking for an efficient way of doing this, since it ended up being a little slow.

Answer 1

A fairly-standard post-order depth-first traversal should work nicely, in linear time on the number of nodes. The main trick is traversing your hydrator tree and data tree together. Post-order means all the dependencies will be instantiated before they're needed higher up. In pseudocode, it would look something like this:

traverse(hydrator_node, json_node)
  for each child of hydrator node
    throw error if json_node doesn't have matching child
    recursively call traverse(hydrator_child, json_child)

  instantiate current node