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: 16 days ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Pre-order	56.9 Ops/sec
Level-order with array	1.9 Ops/sec
Level-order with linked list	663.1 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated 16 days ago):

LLMs can make mistakes. Check important info.

The benchmark provided tests different tree traversal methods in JavaScript, focusing on three approaches: pre-order depth-first search (DFS), and level-order breadth-first search (BFS) using both an array and a linked list. Here's a detailed explanation of the benchmarks, their implementations, and considerations:

### Traversal Approaches

1. **Pre-order (DFS)**:
   - **Implementation**: The `dfs(root)` function uses a generator to yield the root node followed by recursively yielding its children. This results in a depth-first traversal where each node is processed before its children.
   - **Pros**:
     - Memory-efficient for tree structures with high branching; the recursive stack will not grow too large if the tree is balanced.
     - Simple and elegant implementation through a generator.
   - **Cons**:
     - If the tree is extremely deep, this can lead to stack overflow due to excessive recursion.
   - **Use Case**: Suitable for scenarios that require processing a node before its children, like evaluating expressions in parse trees.

2. **Level-order using Array (BFS)**:
   - **Implementation**: The `bfsArray(root)` function utilizes an array to manage the queue of nodes to visit. It processes nodes from the front of the queue and adds their children to the back.
   - **Pros**:
     - Easy to implement and understand; utilizes built-in array methods (like `shift()` and `push()`).
     - All nodes at the current depth are fully processed before moving to the next level.
   - **Cons**:
     - High memory consumption if the tree is wide, as the array can grow large and shifting elements has O(n) complexity in JavaScript arrays.
   - **Use Case**: Useful when the goal is to process all nodes at the same level, such as in pathfinding algorithms.

3. **Level-order using Linked List (BFS)**:
   - **Implementation**: The `bfsLinkedList(root)` function defines a linked list structure to maintain the queue. Each node's children are appended to the end of the list, promoting efficient enqueueing and dequeueing.
   - **Pros**:
     - More memory-efficient than using arrays for wide trees since linked lists do not require space for unused indices.
     - Provides O(1) complexity for adding and removing nodes (`tail` management).
   - **Cons**:
     - More complex to implement than using native arrays, which could lead to increased coding errors or difficulties in understanding.
   - **Use Case**: Preferred when tree width is a concern and memory optimization is critical.

### Performance Results

The benchmark results show that for the current testing environment (Chrome 131 on macOS), the fastest approach was the **Level-order with linked list**, performing at approximately **663.09 executions per second**. This suggests that for the data structure size used (depth 7, branching factor 5), the linked list method was efficient in managing memory while yielding nodes for processing.

Conversely, the **Pre-order traversal** yielded nearly **56.86 executions per second**, and **Level-order using an array** was the slowest at about **1.94 executions per second**. This substantial difference highlights the inefficiency of array-based level-order traversal in terms of both memory and processing speed, especially at a significant tree width.

### Other Considerations

- **Tree Structure**: The benchmark uses a random tree structure generated by `makeRandomTree(depth, degree)`, which replicates varying depths and branching to test the algorithms under different conditions.
  
- **Alternatives**: Other traversal methodologies include:
  - **Post-order Traversal**: Similar to pre-order but processes children before their parent.
  - **Iterative versions of DFS and BFS**: Both can be implemented to avoid the potential pitfalls of recursion depth.
  - **Using Libraries**: Libraries such as Lodash or RxJS may offer utility functions for tree traversal, though they may introduce overhead and dependencies.

Overall, the benchmark’s evaluation of tree traversal methods provides essential insights into their performance characteristics, guiding developers in selecting the most suitable approach for their specific applications and constraints.

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: 16 days 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>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated 16 days ago):