How to build, traverse and map simple trees

Trees have funny definitions like this:

A tree is either nothing or something creating more trees.

Here is some terminology.

Node.A structure holding some data.
Edge.A connection from a parent node to a child node.
Parent of a node X.Any node that creates X.
Child of a node X.Any node that is created by X.
Degree of a node X.Number of children of X.
Sibling of a node X.Any node which is another child of a parent of X.
Ancestor of a node X.Any node that is a parent of X or an ancestor of a parent of X.
Descendant of a node X.Any node that is a child of X or a descendant of a child of X.
Root node.Any node without parents.
Leaf node.Any node without children.
Internal node.Any node which is not a root nor a leaf.
Level of a node X.1 + Number of edges from a root to X.
Height of a node X.Number of edges from X to a leaf.

We call simple trees those trees where there is only one root and all other nodes have only one parent. There are many things that would be better represented by trees with multiple roots and multiple parents. Unfortunately their complexity is not really different from directed acyclic graphs, so the former are seen as a special case of the latter and treated accordingly.

Building

In JavaScript, we can build simple trees like this:

function Node(contents, children) {
    return {
        contents: contents || {},
        children: children || []
    };
}

var tree =
    Node(1, [
        Node(2, [
            Node(5),
            Node(6)
        ]),
        Node(3),
        Node(4, [
            Node(7)
        ])
    ]);

console.log(tree);

whose console output is:

simple tree

Usually we create trees for storing data together with their hierarchical relationships to other data. For example, a thesaurus easily fits into a tree. In fact, we can even define a thesaurus as a tree-like structure:

A thesaurus is either nothing or something creating a narrower thesaurus, and relating to some other thesaurus.

Thus a thesaurus is just a tree together with an additional generic relationship between its nodes.

Traversing

A tree traversal is maybe the most common operation for a tree, regarded as a collection of nodes. Each node is visited once, and there are many possible ways to do it orderly. One of the most common ways is to traverse in depth first order, i.e. starting from the root, we visit a node and each of its children. For example, in our tree (1(2(5,6),3,4(7))), a depth first traversal would visit in order: 1,2,5,6,3,4,7. It’s easy to understand why it’s a very common traversal. It’s not a coincidence that the order is the same we would get by erasing the structure.

Here is a bit of JavaScript code for traversing a tree in depth first order.

function TreeTraversal(tree) {

    var _limit = 0;

    var _index = 0;

    var _self = {
        limit: limit,
        each:  each,
        map:   map,
        tree:  tree
    };

    return _self;

    //---

    // reads / writes the maximum number of nodes to visit
    // 0 means unlimited, i.e. visit all nodes
    function limit(at) {
        if (typeof at == 'undefined') {
            return _limit;
        }
        _limit = Math.abs(at) || 0;
        return _self;
    }

    // true if the limit is still to be reached
    function before_limit() {
        return _limit == 0 || _index < _limit;
    }

    // visits each node in a pre-order depth-first traversal
    // the callback gets 'this' set to the current node 
    // the callback gets an argument set to the zero-based index of the node during the traversal
    // the callback can return false to immediately stop the traversal
    function each(callback) {
        var once_more = true;
        _index = 0;
        var remaining_nodes = [tree];

        while( once_more && before_limit() && remaining_nodes.length ) {
            var current_node = remaining_nodes.shift();
            remaining_nodes = current_node.children.concat(remaining_nodes);

            once_more = callback.call(current_node, _index++) !== false;
        }

        return _self;
    }

}

var logit = function (index) {
    console.log(index + ': ' + this.contents + ', rest ' + this.children.length + '.');
};

var myTreeNodes = TreeTraversal(tree);

console.log('--');
myTreeNodes.each(logit);

console.log('--');
myTreeNodes.limit(5).each(logit);

console.log('--');
myTreeNodes.limit(0).each(logit);

The console output is:

traversal-each

Mapping

There are many possible things we can do while traversing a tree. One of the most common is to map nodes’ contents to some transformation so that we get another tree with same structure but different data.

Here is an updated version of TreeTraversal with a new map method.

function TreeTraversal(tree) {

    var _limit = 0;

    var _index = 0;

    var _self = {
        limit: limit,
        each:  each,
        map:   map,
        tree:  tree
    };

    return _self;

    //---

    // reads / writes the maximum number of nodes to visit
    // 0 means unlimited, i.e. visit all nodes
    function limit(at) {
        if (typeof at == 'undefined') {
            return _limit;
        }
        _limit = Math.abs(at) || 0;
        return _self;
    }

    // true if the limit is still to be reached
    function before_limit() {
        return _limit == 0 || _index < _limit;
    }

    // visits each node in a pre-order depth-first traversal
    // the callback gets 'this' set to the current node 
    // the callback gets an argument set to the zero-based index of the node during the traversal
    // the callback can return false to immediately stop the traversal
    function each(callback) {
        var once_more = true;
        _index = 0;
        var remaining_nodes = [tree];

        while( once_more && before_limit() && remaining_nodes.length ) {
            var current_node = remaining_nodes.shift();
            remaining_nodes = current_node.children.concat(remaining_nodes);

            once_more = callback.call(current_node, _index++) !== false;
        }

        return _self;
    }

    // visits each node in a pre-order depth-first traversal
    // the callback gets 'this' set to the current node 
    // the callback gets an argument set to the zero-based index of the node during the traversal
    // the callback gets an argument set to the contents of the current node
    // the callback must return a transformation of the contents of the current node
    // the callback can be left undefined so that no transformation will be applyed
    function map(callback) {

        if (typeof callback == 'undefined') {
            callback = function(index, contents) {
                return contents;
            }
        }
        var nodes_to_create = [];
        var new_tree = [];

        each(function(index) {
            //logit(this);

            var contents = callback.call(this, index, this.contents);
            var new_node = Node(contents, []);
            node_created();

            var degree = this.children.length;
            if (degree) {
                // internal node
                new_tree.push(new_node);
                nodes_to_create.push(degree);
            }
            else {
                // leaf node
                add_child(new_node);
                if (is_last_child()) {
                    nodes_to_create.pop();
                    var last = new_tree.pop();
                    add_child(last);
                }
            }

        });

        return new_tree[0];

        //---

        function logit(node) {
            console.log(JSON.stringify({
                nodes_to_create: nodes_to_create,
                new_tree: new_tree
            }));
        }

        function last(array, value) {
            return array[array.length - 1];
        }

        function node_created() {
            var rest = nodes_to_create.pop();
            if (rest) {
                nodes_to_create.push(--rest);
            }
        }

        function is_last_child() {
            return last(nodes_to_create) == 0;
        }

        function add_child(new_node) {
            last(new_tree).children.push(new_node);
        }

    }

}

var myTreeNodes = TreeTraversal(tree);

console.log('--');
var new_tree = myTreeNodes.map();

console.log('--');
console.log(new_tree);

The console output is exactly the same as the one we got when building tree.

Note that both .each() and .map() of TreeTraversal share the same signature and functionality with .each() and .map() of jQuery respectively.

Here is a jsFiddle if you want to play around.