Javascript Primer: Using Tree Structures To Support Hierarchical Data

Home
ActiveEngine
Javascript Primer: Using Tree Structures To Support Hierarchical Data

Javascript Primer: Using Tree Structures To Support Hierarchical Data

treebeard-the-ent-e1269783419659Organizing data so that you sort, filter or manipulate items efficiently is critical for front end applications.  These days its not enough to have a pretty design – it’s gotta like do some stuff.  Just sayin’.  It would be silly if you had to constantly send requests back to a server just filter them, or sort them in a new order.

Sometimes you might be asked to support hierarchical or nested data.  A perfect example is a project plan: there are levels and nested levels; there is an implied relationship between the parent levels and their children; the order of the list items implies a precession, or a progression.  Consider also thate each list item not only has a task, but also has the duration for that task, and you have to total all the durations for an estimate.  Perhaps your crazy manager asks you to only fetch the tasks where a certain team member works, oh, and by the way, exclude all the tasks that are parent level tasks.  As you can see, there is a need for a structured approach that you can easily re-use.

Simple Nested Structures May Not Be Enough

In general, creating nested data structures is fairly straight forward.  Let’s continue with our scenario of a project plan:


var Task = function (options) {
    var _options = options || {};

    var _description = _options.description || "";
    var _assignedTo = _options.assignedTo || "";
    var _duration = _options.duration || 0.0;

    var _tasks = [];

    return {
        description: _description,
        assignedTo: _assignedTo,
        duration: _duration,
        tasks: _tasks
    };
};

We will represent each project item as a Task that has a description, the team assigned to the task and a duration. The array “_tasks” represents the sub tasks or children of a task. You can indeed represent a hierarchy by simply adding this array and achieving what ever nesting levels that you desire.  This jsFiddle illustrates what that would look like.

While this does the job, how are you going to provide filtering? We need a way to walk the hierarchy; furthermore, we don’t want a one time function for type of traversal. Also, how do we handle the times when we need to affect a change only to items that are two levels deep. Simple recursion will not be enough here.

TreeNodes Can Provide Help

What we need is a data structure that will tell us where we are in the hierarchy of data items; who the parent of an item is, and if there are any children for a particular item. Once we can obtain these, performing operations are much easier, and we can answer questions like “What are all the tasks that over 10 hours” or “what are all the tasks for ‘POC Development’”.  Being able to walk the hierarchy will also give us the capability to automatically calculate the overall hours for a project.

var TreeNode = function (options) {
        var _options = options || {};

        var _value = _options.value || {};
        var _children = _options.children || [];
        var _parent = _options.parent || null;

        //  Public methods
        var isRoot = function () {
            return (_parent == null);
        };

        var level = function () {
            return isRoot() ? 0 : _parent.level() + 1;
        };

        var addChild = function (value) {
            var childNode = new TreeNode({ value: value, parent: this });
            _children.push(childNode);

            return childNode;
        };

        return {
            value: _value,
            children: _children,
            parent: _parent,

            //  public methods
            isRoot: isRoot,
            isLeaf: isLeaf,
            level: level,
            addChild: addChild
        };
    };

Let’s dissect this a bit. A TreeNode will wrap an object; more specifically “_value” will be the container for our Task object. “_children” is an array of TreeNodes that each wrap another Task object. A TreeNode can have a “_parent”, so naturally any item the _children array will “point” back a single TreeNode. This establishes our relationships between tasks and sub-tasks. In some scenarios you have a TreeNode and need to a property for that TreeNode’s parent, and “_parent” offers that convenience.

The function “isRoot()” tells us that we are at the top of a hierarchy. “level()” tells us what level a TreeNode sits at. Looking at this code you’ll note that it relies on “isRoot()” to determine whether to return a 0 or simply increment the “_parent.level”. To create your hierarchy, simple call TreeNode.addChild(new Task);

If you look at the jsFiddle you’ll see that we have a hierarchy established, and the path of “Check Team Schedule” can represented as tasks[3].tasks[0].tasks[2].  If we were to set a variable to tasks[3].tasks[0].tasks[2] we are disconnected from our hierarchy, as the individual items sitting in each “tasks” array are unaware of their parents.  In order for us to start any filtering or querying, we will first have to pull the tasks apart and re-assemble them as TreeNodes.  Luckily we can create a function to build a tree from our Task objects:

var treeFuncs = function(){
    var buildTaskTree = function (sourceTasks) {
        var tree = new TreeNode({
            value: "ROOT"
        });

        var taskStack = [];
        var treeNodeTargetStack = [];

        taskStack.push(sourceTasks);
        treeNodeTargetStack.push(tree);

        while (taskStack.length > 0) {
            var currentTask = taskStack.pop();
            var targetNode = treeNodeTargetStack.pop();

            var length = currentTask.length;
            for (var i = 0; i < length; i++) {
                var task = currentTask[i];
                var childNode = targetNode.addChild(task);

                if (task.tasks.length > 0) {
                    taskStack.push(task.tasks);
                    treeNodeTargetStack.push(childNode);
                }
            }
        }

        return tree;
    };

    return {
        buildTaskTree: buildTaskTree
    };
};

The function buildTaskTree accepts an array of Task objects. Next, we will create a root for our TreeNodes, and all other child TreeNodes will be added to this variable. Instead of using recursion, we will create two stacks “taskStack”, where we will store all the Task objects, and “treeNodeTargetStack” will hold the current TreeNode that will receive new children. Note that we are “seeding” the “taskStack” with the incoming array of Task objects. “targetTreeStack” will have the “tree” variable that is the root of the tree that we are building.

The while loop will always pull from the taskStack; more specifically, the first pass will have the top level tasks “Discuss Product Concept”, “Create Mockups”, “Setup POC environment”, “POC Development” from our project plan. We look at each item and add it to the current position of the tree. If the current Task has children we will want to do two things:

  1. Push the child tasks array onto the “taskStack”. When we execute the loop again, it will pick up this new entry and continue our processing.
  2. Push the newly created child TreeNode onto the treeNodeTargetStack so that we maintain the hierarchy between the tasks. The next time we execute the while loop, we are the current TreeNode and add to its children. This maintains our hierarchy relationships.

That’s it. Each subsequent pass of the while loop drives deeper into Tasks hierarchy as each child is added to “taskStack”. When we’re done, we return “tree” as our TreeNode structure.

How To Put TreeNodes To Good Use

Great. We have TreeNodes. Now what? Well, our goal was to create structure that we could traverse and always know who our parent was, and who our children were, as well as creating the ability to determine what level in the hierarchy we are located.  To find answers to questions that require us to filter, sort, etc we will visit each node on the TreeNode structure, and at each stop we will perform a function that will act as our query and record the result for that node.  When the trip is done we’ll have a subset of our tree.

First the function that walks the TreeNode:


var traverseAndApply = function (treeNode, func, functionArgs) {
        var treeNodeStack = [];
        var rootArray = [];
        rootArray.push(treeNode);

        treeNodeStack.push(rootArray);

        while (treeNodeStack.length > 0) {
            var currentNodeList = treeNodeStack.pop();
            var length = currentNodeList.length;

            for (var i = 0; i < length; i++) {
                var currentNode = currentNodeList[i];
                if (currentNode.parent != null) {
                    func(currentNode.value, currentNode, functionArgs);
                }

                if (currentNode.children.length > 0) {
                    treeNodeStack.push(currentNode.children);
                }
            }
        }
    };

The function traverseAndApply accepts three arguments. The argument “func” is a function, and this is the function that will executed at each node in the TreeNode. “functionArgs” are the items that will be pass into the “func”. The remainder of his function may look familiar – the approach is the same as in buildTaskTree. Again, we are avoiding recursion and are using the stack approach. We push the TreeNode to an array, then push the array onto a stack. As we loop, we pull each TreeNode, fire off “func”, then progress to the next.

So let’s put this to use. Our first example will be to find all tasks that are the top level tasks, in the parlance of our TreeNode, where the TreeNode.level() is equal to 1.


var treeNode = _treeFuncs.buildTaskTree(_tasks);

        var matchTopLevelArgs = {};
        matchTopLevelArgs.results = []

        var matchTopLevelFunc = function(value, node, funcArgs){
            if(node.level() == 1){
                funcArgs.results.push(value);
            }
        };

        _treeFuncs.traverseAndApply(treeNode, matchTopLevelFunc, matchTopLevelArgs);

And now let’s find all of Frodo’s tasks that are not top level tasks:

var treeNode = _treeFuncs.buildTaskTree(_tasks);

        var frodoTasksArgs = {};
        frodoTasksArgs.results = [];

        var frodoTasksFunc = function(value, node, funcArgs){
            if((value.assignedTo.indexOf("Frodo") > -1) & (node.level() != 1)){
                funcArgs.results.push(value);
            }
        };

In our jsFiddle you’ll find working versions of the above filter examples. Experiment around and see what you can come up with.

Future Considerations

Now that we have the basics down you can see that we have a very powerful tool. No doubt you have noticed that the hours for our project don’t make sense, as normally the duration of a task is comprised of the duration of any sub-tasks. Since we can visit each node, we may be able to devise a way to create a function that can calculate the duration for each level appropriately.

Another idea could also be the ability to change a task to sub-task or maybe make a sub-task into a new parent.  Our ability to manipulate the TreeNode and it’s underlying data can go a long for us.  So that’s what we will explore next time.  Until then, play the video below and enjoy some tree music.

ActiveEngine Software
About The Author
ActiveEngine Sensei is soley responsible for his remarks.

There are no comments yet, but you can be the first



Leave a Reply



ActiveEngine Software by ActiveEngine, LLC.