Tree with auto-get-depth

README.md

Tree with Automatic Get-Depth

Meant for very large tree-sets, yea? This tree is aimed at implementing an idea that the depth of a tree can be known from the root-node without a breadth-first or depth-first search.

Every time a node is updated on the tree, it increases the depth-count of its parent, which also increases the depth count of its parent in a recursive manner, so the depth of the entire tree is always known from the root-node.

Ofcourse, this is only a prototype, and i'll be happy to accept notes on improving the algorithm.

Notes for Improvement

• For now, nodes are only added and not removed.
• The Nodes could extend the array prototyping instead of having the property children which could be manipulated, thus defeating the purpose.

auto-get-depth-tree.js

function Node() {
    this.children = [];
    this.depth = 0;
    var me = this;
    this.hasChildren = function () {
        return me.children.length > 0;
    }
    this.addNode = function (item) {
        item = item || new Node();
        me.children.push(item);
        item.registerParent(me);
        if (me.children.length == 1) item.addDepth(0);
    }
    this.addDepth = function (plus) {
        plus = plus || 0;
        if (me.hasChildren()) me.depth = Math.max(plus, me.depth);
        plus += 1;
        if (me.parent()) me.parent().addDepth(plus);
    }
    this.registerParent = function (parent) {
        me.parent = function () {
            return parent;
        }
    }
    me.parent = function () {
        return null;
    }
}

function insertNodes(node, count) {
    count = count || 3;
    node = node || new Node();
    for (var i = 0; i < count; i++) {
      node.addNode(new Node());
    }
    return node;
}

function getSampleTree() {
    var root = new Node();
    root = insertNodes(root);
    root.children[0] = insertNodes(root.children[0]);
    root.children[1] = insertNodes(root.children[1]);
    root.children[2] = insertNodes(root.children[2]);//depth is 2
    root.children[0].children[0] = insertNodes(root.children[0].children[0]); //depth is 3
    //root.children[0].children[0].children[0] = insertNodes(root.children[0].children[0].children[0]); //depth is 4
    //root.children[0].children[0].children[1] = insertNodes(root.children[0].children[0].children[1]); //depth is still 4
    return root;
}

Fixed bug pointed out by @blaise-zaga where adding another child node to a node with an existing child would still update depth and increment it.
Fix: No more incrementation ... depth updates using Math.max instead