const MAX_NODE_COUNT = 100000; function createWideTree() { var root = { n: 1, children: [] }; for(var i=2; i<=MAX_NODE_COUNT; i++) { root.children.push({ n: i }); } return root; } var root = createDeepTree(); function* breadthTraversalTree(root) { const rootChildren = root.children; yield root; while(rootChildren.length) { let firstChild = rootChildren.shift(); yield firstChild; if(firstChild.children) { rootChildren.push(...firstChild.children); } } } source tree (root = 1): * * 1 * / | \ * 2 3 4 * / \ \ => { 1, 2, 3, 4, 5, 6, 7, 8 } * 5 6 7 * | * 8
  • What is this algorithm? what is he doing? for what input data? - Grundy
  • Accepts the binary tree root and returns the sequence of all tree nodes in breadth-first order. - Vitalik Mileshko
  • sequence of all tree nodes in breadth-first order - what does this mean? :-) - Grundy
  • in general, notice that your input object is spoiling. And although it is generally not clear what you are doing with the input object. If you only need to output a sequence, why change the object itself? - Grundy
  • Add an example of the input data, and an example of the appropriate output: to edit the question, use the edit button under the question - Grundy

1 answer 1

I made it through a double linked list, it was possible through a single sheet, but I just had predetermined methods.

 class Node { constructor(data = null, prev = null, next = null) { this.data = data; this.prev = prev; this.next = next; } } class LinkedList { constructor() { this.length = 0; this._head = null; this._tail = null; } append(data) { var node = new Node(data); if (this.length === 0) { this._head = node; this._tail = node; } else { this._tail.next = node; node.prev = this._tail; this._tail = node; } this.length++; return this; } nodeAt(index) { var currentNode = this._head; var length = this.length; var count = 0; var message = { failure: 'Failure: non-existent node in this list.' }; if (length === 0 || index < 0 || index > length) { throw new Error(message.failure); } while (count < index) { currentNode = currentNode.next; count++; } return currentNode; } deleteAt(index) { if (this.length === 0) { return; } if (index < 0 || index >= this.length) { var message = { failure: 'Failure: non-existent node in this list.' }; throw new Error(message.failure); } if (this.length === 1) { this._head.data = null; this._tail.data = null; } else if (index === 0) { this.nodeAt(1).prev = null; this._head = this.nodeAt(1); } else if (index === this.length - 1) { this.nodeAt(index - 1).next = null; this._tail = this.nodeAt(index - 1); } else { this.nodeAt(index - 1).next = this.nodeAt(index + 1); this.nodeAt(index + 1).prev = this.nodeAt(index - 1); } this.length--; return this; } } function* breadthTraversalTree(root) { let queue = new LinkedList(); queue.append(root); while (queue.length) { let n = new Node(); n.data = queue._head.data; queue.deleteAt(0); if (n.data.children) { n.data.children.forEach(x => queue.append(x)); } yield n.data; } }