Here’s one way (BFS) to create a linked list for every depth of a binary tree in JavaScript:
listOfDepthsTry in REPL1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| function listOfDepths(root) { if (!root) return; const result = []; const queue = []; queue.push(root); let level = 0; while (queue.length) { const treeNode = queue.shift(); const list = new List(treeNode.value); if (treeNode.left) { queue.push(treeNode.left); } if (treeNode.right) { queue.push(treeNode.right) } for (let i = 2; i <= Math.pow(2, level) && queue.length; i++) { const tNode = queue.shift(); if (tNode.left) { queue.push(tNode.left); } if (tNode.right) { queue.push(tNode.right) } list.addToTail(tNode.value); } result.push(list) level++; } return result; } function List(value) { this.value = value; this.next = null; } List.prototype.addToTail = function(value) { let node = this; while (node.next) { node = node.next; } node.next = new List(value); }
|
Tests can be found at REPL.it