3
\$\begingroup\$

This question is the second version of the code here.

I'm writing a general tree class. Specifically, each node should have oen parent, some number of children, and hold a value.

I'm looking for general advice on how to make this code more idiomatic. I'm also looking for thoughts on the traverse function, any functions that should be present in a general tree class but aren't, and also any way to simplify the existing functions.

// Code to review
class Node {
	constructor(value = 0, children = []) {
		this.value = value;
		this.children = children;
	}

	traverse({ preorder, postorder, levelorder }) {
		if (levelorder) {
			let nodes = [this];
			while (nodes.length > 0) {
				const current = nodes.shift();
				levelorder(current);
				nodes = nodes.concat(current.children);
			}
		}
		else {
			if (preorder) preorder(this);
			this.children.forEach(n => n.traverse({ preorder, postorder }));
			if (postorder) postorder(this);
		}
		return this;
	}

	clone() {
		const copy = n => Object.assign(new Node(), n);
		let that = copy(this);
		that.traverse({ preorder: n => n.children = n.children.map(copy) });
		return that;
	}

	map(callback) {
		let that = this.clone();
		that.traverse({ levelorder: n => n.value = callback(n.value) });
		return that;
	}

	reduce(callback, initial) {
		let a = initial;
		this.traverse({	levelorder: n => a = (n === this && initial === undefined)? n.value: callback(a, n.value) });
		return a;
	}

	filter(callback) {
		let that = this.clone();
		that.traverse({ levelorder: n => n.children = n.children.filter(m => callback(m.value)) });
		return that;
	}

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

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

	find(callback) {
		return this.reduce((a, b) => (callback(b)? a.push(b): null, a), []);
	}

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

// Testing code
let tree = new Node(0);
let a = new Node(1);
let b = new Node(2);
let c = new Node(3);
let d = new Node(4);
let e = new Node(5);
let f = new Node(6);
tree.children = [a, b, c];
a.children = [d];
d.children = [e, f];

console.log("\nmap", tree.map(a => a + "2"));
console.log("\nreduce", tree.reduce((a, b) => String(a) + String(b)));
console.log("\nfilter", tree.filter(a => a < 3));

console.log("\nevery", tree.every(a => a < 3));
console.log("\nsome", tree.some(a => a < 3))

console.log("\nfind", tree.find(a => a > 2));
console.log("\nincludes", tree.includes(3));

\$\endgroup\$
2
\$\begingroup\$

Review

Well written API, but I am not happy with this one:

traverse({ preorder, postorder, levelorder })

preorder and postorder can be combined, but they are always mutually exclusive with levelorder.

traverse({ preorder, postorder, levelorder }) {
  if (levelorder) {
      // levelorder ..
  }
  else {
      // preorder conditional and/or postorder conditional ..
  }
  return this;
}

Instead, use 2 separate methods, each doing their own well known type of traversal.

DFS

 traverseDepthFirst({ preorder, postorder })

BFS

 traverseBreadthFirst({ levelorder })

Some general thoughts:

  • should you allow cyclic graphs?
  • should you want to traverse up the ancestors?
\$\endgroup\$

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.