3
\$\begingroup\$

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);
};
\$\endgroup\$
  • \$\begingroup\$ Hello, could you maybe explain in more detail what your tree structure is, because there are many of them. This would help having a better review. \$\endgroup\$ – IEatBagels Aug 23 at 20:10
  • \$\begingroup\$ The goal is to provide an extremely general tree. Each node should have one parent, some number of children, and hold a value. \$\endgroup\$ – Alex F Aug 23 at 20:11
  • \$\begingroup\$ Alright that's a pretty good explanation, you should add it to your post. There's a close vote on your question, I suspect this is the reason. I wouldn't worry if I were you, in the event your question was to get closed, I'm sure it would be reopened, it's a good question. \$\endgroup\$ – IEatBagels Aug 23 at 20:13
  • \$\begingroup\$ How can I know if my question has a close vote? \$\endgroup\$ – Alex F Aug 23 at 20:19
  • 1
    \$\begingroup\$ here's a post about it: codereview.meta.stackexchange.com/questions/8744/… \$\endgroup\$ – dfhwze Aug 23 at 20:29
3
\$\begingroup\$

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 JS/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;
  }

  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);
  }
  
}

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));
    }
};


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)

\$\endgroup\$
  • \$\begingroup\$ Is there a way to move Node.traversal inside the class block? It feels weird and too separate from the rest of the functions right now. \$\endgroup\$ – Alex F Aug 23 at 21:06
  • \$\begingroup\$ I agree that it's odd. It's one of the many reasons that I don't like the current class syntax. There is now a widely supported static method syntax, but nothing for other properties. I've never really tried to learn why. \$\endgroup\$ – Scott Sauyet Aug 25 at 0:50
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ inorder traversal makes sense only for a binary tree. \$\endgroup\$ – Scott Sauyet Aug 23 at 19:05
  • \$\begingroup\$ @ScottSauyet For me, the pre- and post-order are the most important ones. The in-order probably doesn't have that many applications here. I would agree with you. \$\endgroup\$ – dfhwze Aug 23 at 19:15
  • 1
    \$\begingroup\$ I do use inorder reasonably often, but it simply makes no sense when you don't have specific left and right children. \$\endgroup\$ – Scott Sauyet Aug 23 at 20:00
  • \$\begingroup\$ If I am going to add postorder traversal, would it make sense to split traverse into two different functions (one for breadth-first and one for depth-first)? \$\endgroup\$ – Alex F Aug 23 at 20:12
  • 2
    \$\begingroup\$ But I wouldn't split all other methods into different search strategy and order. Does it really matter how you search for items (maybe it does)? But when executing actions when walking the tree, strategy and order definately must be available parameters/split methods. \$\endgroup\$ – dfhwze Aug 23 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.