Categories: JavaScript

Let’s do this one more time – this time with JS.  Here is a constructor function for a generic tree node that has one parent and possibly N children:

var TreeNode = function (data) {
    this.parent = data.parent || null;
    this.children = data.children || [];
};

TreeNode.prototype.isLeaf = function () {
    return this.children.length == 0;
};

TreeNode.prototype.isRoot = function () {
    return this.parent == null;
};

Here is how we’d traverse the tree with a depth-first search (note that I’m using the underscore.js library for the each() function – you could also use ES5’s Array.forEach() if you do not want to support older browsers – or use a polyfill):

function visitDfs(node, func) {
    if (func) {
        func(node);
    }

    _.each(node.children, function (child) {
        visitDfs(child, func);
    });
}

Doing a breadth-first traversal is also straightforward thanks to JavaScript’s Array class and its queue/stack-like functionality:

function visitBfs(node, func) {
    var q = [node];
    while (q.length > 0) {
        node = q.shift();
        if (func) {
            func(node);
        }

        _.each(node.children, function (child) {
            q.push(child);
        });
    }
}

Finally, let’s do something tangible with a depth-first traversal.  In the next code snippet, the prune() function will prune out nodes that are single children to their parents in order to collapse the tree into a simpler structure.  This will eliminate groupings of nodes that aren’t really grouping anything because their branching factor is 1:

function prune(root) {
    visitDfs(root, function (node) {
        if (node.isRoot()) {
            return; // do not process roots
        }
        if (node.children.length == 1 && !node.children[0].isLeaf()) {
            var child = node.children[0],
                index = _.indexOf(node.parent.children, node);
            node.parent.children[index] = child;
            child.parent = node.parent;
        }
    });
}

This code works by doing a DFS and calling a function on each node.  That function examines the node to see if it has exactly one child and that the one child node is not a leaf (we don’t want to prune out leaves or roots).  If it is, the child node is extracted out and assigned to the node’s parent’s children and then the child’s parent is reassigned to the node’s parent.  This effectively eliminates (prunes) the node out of the tree collapsing it into a simpler structure.

No Comments