Javascript Tree Class

Question

I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value.

I'm mostly looking for advice on how to make this code more idiomatic, but also functionality that might be missing from this class, or that isn't necessary. I would also like thoughts on how idiomatic the traverse function is, and if there's a better way to implement it.

function Node(value = 0, children = []) {
    this.value = value;
    this.children = children;
    this.parent = undefined;
}

Node.from = function(node) {
    let that = Object.assign(new Node(), node);
    that.parent = undefined;
    that.children = node.children.map(n => (Node.from(n), n.parent = that));
    return that;
};

Node.prototype.add = function(...children) {
    for (child of children) {
        child.parent = this;
        this.children.push(child);
    }
};

Node.Traversal = {
    BreadthFirst: 1,
    DepthFirst: 2
};

Node.prototype.traverse = function(callback, mode = Node.Traversal.BreadthFirst) {
    if (mode == Node.Traversal.BreadthFirst) {
        let nodes = [this];
        while (nodes.length > 0) {
            const current = nodes.shift();
            callback(current);
            nodes = nodes.concat(current.children);
        }
    } else if (mode == Node.Traversal.DepthFirst) {
        callback(this);
        this.children.forEach(n => n.traverse(callback, false));
    }
    return this;
};

Node.prototype.reduce = function(callback, initial, mode) {
    let acc = initial;
    this.traverse(n => acc = callback(acc, n), mode);
    return acc;
};

Node.prototype.every = function(callback) {
    return this.reduce((a, n) => a && callback(n), true);
};

Node.prototype.some = function(callback) {
    return this.reduce((a, n) => a || callback(n), false);
};

Node.prototype.find = function(callback, mode) {
    return this.reduce((a, n) => a || (callback(n)? n: false), false, mode);
};

Node.prototype.includes = function(value) {
    return this.some(n => n.value === value);
};

Answer 1

This is overall well-thought-out, well-organized, and well-written.

There's at least one bug, and one oversight that I would consider a bug:

• In traverse your recursive call is passing the wrong second parameter:

  } else if (mode == Node.Traversal.DepthFirst) {
      callback(this);
      this.children.forEach(n => n.traverse(callback, false));
  }

  should read

  } else if (mode == Node.Traversal.DepthFirst) {
      callback(this);
      this.children.forEach(n => n.traverse(callback, Node.Traversal.DepthFirst));
  }

• in add you don't declare child. Presumably is should read for (let child of children)

As to design decisions, there are several things you might want to consider.

• add might be improved with return this.

• I think a clone method might be a more common choice here than a static from function.

• You might find the ES6 class syntax slightly more explicit. I wasn't a big fan of it when it was proposed, and I'm still not; I don't like the implication it suggests that JS OOP is particularly similar to Java/C# style OOP. But it does carry a bit less cruft than the constant repetition of Node.prototype.

• Rather than use an enumeration of traversal types, you might want to consider simply using functions instead. That is,

  Node.Traversal = {
      BreadthFirst: function(callback) {
          let nodes = [this];
          while (nodes.length > 0) {
              const current = nodes.shift();
              callback(current);
              nodes = nodes.concat(current.children);
          }      
      },
      DepthFirst: function(callback) {
          callback(this);
          this.children.forEach(n => n.traverse(callback,  Node.Traversal.DepthFirst));
      }
  };
  
  Node.prototype.traverse = function(callback, traversal = Node.Traversal.BreadthFirst) 
  {
      traversal.call(this, callback);
      return this;
  };
  

  This would make it easier for you to add another traversal, since you only have to do it in one place, and it lets users supply their own instead.

• Perhaps most importantly, you might want to drop the parent property. You do not use it anywhere except in building or cloning a tree, and it can lead to real problems. For instance, if you cloned a tree with from (and therefore ended up with non-empty parent nodes), you will not be able to call JSON.stringify on it due to the cyclic nature.

Putting this all together, here's an alternate version:

console.clear() 

class Node {
  constructor (value = 0, children = []) {
    this.value = value;
    this.children = children;
  }
  
  static Traversal = {
    BreadthFirst: function(callback) {
        let nodes = [this];
        while (nodes.length > 0) {
            const current = nodes.shift();
            callback(current);
            nodes = nodes.concat(current.children);
        }      
    },
    DepthFirst: function(callback) {
        callback(this);
        this.children.forEach(n => n.traverse(callback,  Node.Traversal.DepthFirst));
    }
  }
  
  clone () {
    let that = Object.assign(new Node(), this);
    that.children = this.children.map(n => n.clone());
    return that;
  }
  
  add (...children) {
    for (let child of children) {
      this.children.push(child);
    }
    return this;
  }

  traverse (callback, traversal = Node.Traversal.BreadthFirst) {
    traversal.call(this, callback);
    return this;
  }

  reduce (callback, initial, mode) {
    let acc = initial;
    this.traverse(n => acc = callback(acc, n), mode);
    return acc;
  }

  every (callback) {
    return this.reduce((a, n) => a && callback(n), true);
  }

  some (callback) {
    return this.reduce((a, n) => a || callback(n), false);
  }

  find (callback, mode) {
    return this.reduce((a, n) => a || (callback(n)? n: false), false, mode);
  }

  includes (value) {
    return this.some(n => n.value === value);
  }  
}

const tree = new Node ('A', [
  new Node('  B', [
    new Node('    D'),
    new Node('    E', [
      new Node('      G'),
    ]),
    new Node('    F')
  ]),
  new Node('  C') 
])

tree.children[0].children[2].add(new Node('      H')).add(new Node('      I'))

const log = ({value}) => console.log(value)
console.log('===============================')
console.log('Breadth-first')
console.log('===============================')
tree.traverse(log)
console.log('===============================')
console.log('Depth-first')
console.log('===============================')
tree.traverse(log, Node.Traversal.DepthFirst)
console.log('===============================')
console.log('Clone, Breadth-first')
console.log('===============================')
tree.clone().traverse(log)
console.log('===============================')
console.log('Clone, Depth-first')
console.log('===============================')
tree.clone().traverse(log, Node.Traversal.DepthFirst)

Answer 2

Review

• Your code is compact and well organised. Reusing traverse and reduce allows for easy extensibility.
• Your tree could be a graph, or even worse a cyclic one: traverse could iterate to infinity.
• By adding additional methods such as descendants and ancestors you could guard that the structure remains a tree. When adding a node, it cannot have a parent, it cannot be the node self, it cannot be a descendant or an ancestor.
• You're allowing BFS and DFS, but only in pre-order. I would also include post-order (and perhaps also in-order).
• Adding additional properties in a node might be useful for certain use cases: root, depth, height, isleaf, isbranch