Run results for: Traverse Tree Pre-Orderly, Level-Orderly using Array, and Level-Orderly using Linked List

Run details:

User agent: Mozilla/5.0 (iPhone; CPU iPhone OS 16_3_1 like Mac OS X) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/16.3 Mobile/15E148 Safari/604.1

Browser: Mobile Safari 16

Operating system: iOS 16.3.1

Device Platform: Mobile

Date tested: one year ago

Level-order with linked list

239/s

Level-order with array

51/s

Pre-order

11/s

View exact numbers

Test name	Executions per second
✓ Level-order with linked list	239 Ops/sec
Level-order with array	51 Ops/sec
Pre-order	11 Ops/sec

Script Preparation code:

function *dfs(root) {
    yield root;
    for (let child of root.children) {
        yield *dfs(child);
    }
}


function *bfsArray(root) {
    let queue = [root];
    do {
        let node = queue.shift();
        yield node;
        queue.push(...node.children);
    } while (queue.length);
}


function *bfsLinkedList(root) {
    let head = {node: root, next: null};
    let tail = head;

    do {
        let node = head.node;
        yield node;

        for (let child of node.children) {
            tail = tail.next = {node: child, next: null};
        }

        head = head.next;
    } while (head !== null);
}


function makeRandomTree(depth, degree) {
    let node = {
        data: Math.round(Math.random() * 100),
        children: []
    };

    if (depth !== 0)
    for (let i = 0; i < degree; ++i) {
        node.children.push(makeRandomTree(depth - 1, degree));
    }

    return node;
}

const testTree = makeRandomTree(7, 5);

Tests:

Pre-order
for (let node of dfs(testTree)) {node.data;}
Level-order with array
for (let node of bfsArray(testTree)) {node.data;}
Level-order with linked list
for (let node of bfsLinkedList(testTree)) {node.data;}