EXERCISE · AlgoCasts
Level width
Given the root node of a tree, return an array where each element is the width of the tree at each level.
Directions
Directions
Given the root node of a tree, return an array where each element is the width of the tree at each level.
Examples#
JS
Given: 0/ | \1 2 3| |4 5Answer: [1, 3, 2]Try it first#
Copy the stub, make the 3 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.
JSexercises/levelwidth/index.js
function levelWidth(root) {} module.exports = levelWidth;Solution#
JScompleted_exercises/levelwidth/index.js
function levelWidth(root) { const arr = [root, 's']; const counters = [0]; while (arr.length > 1) { const node = arr.shift(); if (node === 's') { counters.push(0); arr.push('s'); } else { arr.push(...node.children); counters[counters.length - 1]++; } } return counters;} module.exports = levelWidth;const Node = require('./node');const levelWidth = require('./index'); test('levelWidth is a function', () => { expect(typeof levelWidth).toEqual('function');}); test('levelWidth returns number of nodes at widest point', () => { const root = new Node(0); root.add(1); root.add(2); root.add(3); root.children[0].add(4); root.children[2].add(5); expect(levelWidth(root)).toEqual([1, 3, 2]);}); test('levelWidth returns number of nodes at widest point', () => { const root = new Node(0); root.add(1); root.children[0].add(2); root.children[0].add(3); root.children[0].children[0].add(4); expect(levelWidth(root)).toEqual([1, 1, 2, 1]);}); module.exports = class Node { constructor(data) { this.data = data; this.children = []; } add(data) { this.children.push(new Node(data)); }}; 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 levelwidth inside the fork.
See also