EXERCISE · AlgoCasts
Tree
1) Create a node class. The constructor should accept an argument that gets assigned to the data property and initialize an empty array for storing children.
Directions
1) Create a node class. The constructor should accept an argument that gets assigned to the data property and initialize an empty array for storing children. The node class should have methods 'add' and 'remove'. 2) Create a tree class. The tree constructor should initialize a 'root' property to null. 3) Implement 'traverseBF' and 'traverseDF' on the tree class. Each method should accept a function that gets called with each element in the tree
Try it first#
Copy the stub, make the 7 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.
class Node {} class Tree {} module.exports = { Tree, Node };Solution#
class Node { constructor(data) { this.data = data; this.children = []; } add(data) { this.children.push(new Node(data)); } remove(data) { this.children = this.children.filter(node => { return node.data !== data; }); }} class Tree { constructor() { this.root = null; } traverseBF(fn) { const arr = [this.root]; while (arr.length) { const node = arr.shift(); arr.push(...node.children); fn(node); } } traverseDF(fn) { const arr = [this.root]; while (arr.length) { const node = arr.shift(); arr.unshift(...node.children); fn(node); } }} module.exports = { Tree, Node };const T = require('./index');const Node = T.Node;const Tree = T.Tree; describe('Node', () => { test('Node is a constructor', () => { expect(typeof Node.prototype.constructor).toEqual('function'); }); test('Node has a data and children properties', () => { const n = new Node('a'); expect(n.data).toEqual('a'); expect(n.children.length).toEqual(0); }); test('Node can add children', () => { const n = new Node('a'); n.add('b'); expect(n.children.length).toEqual(1); expect(n.children[0].children).toEqual([]); }); test('Node can remove children', () => { const n = new Node('a'); n.add('b'); expect(n.children.length).toEqual(1); n.remove('b'); expect(n.children.length).toEqual(0); });}); describe.skip('Tree', () => { test('starts empty', () => { const t = new Tree(); expect(t.root).toEqual(null); }); test('Can traverse bf', () => { const letters = []; const t = new Tree(); t.root = new Node('a'); t.root.add('b'); t.root.add('c'); t.root.children[0].add('d'); t.traverseBF(node => { letters.push(node.data); }); expect(letters).toEqual(['a', 'b', 'c', 'd']); }); test('Can traverse DF', () => { const letters = []; const t = new Tree(); t.root = new Node('a'); t.root.add('b'); t.root.add('d'); t.root.children[0].add('c'); t.traverseDF(node => { letters.push(node.data); }); expect(letters).toEqual(['a', 'b', 'c', 'd']); });}); Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest tree inside the fork.
See also