Benchmark: Traverse Tree Pre-Orderly, Level-Orderly using Array, and Level-Orderly using Linked List

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;}

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Pre-order
Level-order with array
Level-order with linked list

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 8 months ago)

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

Browser/OS: Firefox 142 on Linux

View result in a separate tab

Test name	Executions per second
Pre-order	14.9 Ops/sec
Level-order with array	82.9 Ops/sec
Level-order with linked list	65.5 Ops/sec

Related benchmarks:

Traverse Tree Pre-Orderly, Level-Orderly using Array, and Level-Orderly using Linked List (version: 1)

Comparing performance of: Pre-order vs Level-order with array vs Level-order with linked list

Created: one year ago by: Guest

Jump to the latest result

Pre-order

Level-order with array

Level-order with linked list

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A