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

Run details:

User agent: Mozilla/5.0 (X11; Linux x86_64; rv:142.0) Gecko/20100101 Firefox/142.0

Browser: Firefox 142

Operating system: Linux

Device Platform: Desktop

Date tested: 11 months ago

Level-order with array

83/s

Level-order with linked list

66/s

Pre-order

15/s

View exact numbers

Test name	Executions per second
✓ Level-order with array	83 Ops/sec
Level-order with linked list	66 Ops/sec
Pre-order	15 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;}