Benchmark: Tree Traversals - MeasureThat.net

Script Preparation code:

root = {val: 1001}
let i = 0, node = root
while (++i < 1000) {
  while (node) {
    if (i < node.val) {
      if (!node.left) {
        node.left = { val: i }
        break
      }
      node = node.left
    } else {
      if (!node.right) {
        node.right = { val: i }
        break
      }
      node = node.right
    }
  }
}

Tests:

DFS
function dfs(node) { if (!node) return dfs(node.left) dfs(node.right) } dfs(root)
BFS (shift)
let q = [root] while (q.length) { const node = q.shift() if (node.left) q.push(node.left) if (node.right) q.push(node.right) }
BFS (pop)
let q = [root] while (q.length) { const node = q.pop() if (node.right) q.push(node.right) if (node.left) q.push(node.left) }
BFS (reassign queue)
let q = [root] while (q.length) { const level = [] const node = q.pop() if (node.left) level.push(node.left) if (node.right) level.push(node.right) q = level }
BFS (reassign node, shift)
let q = [], node = root while (node) { if (node.left) q.push(node.left) if (node.right) q.push(node.right) node = q.shift() }
BFS (reassign node, pop)
let q = [], node = root while (node) { if (node.right) q.push(node.right) if (node.left) q.push(node.left) node = q.pop() }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
DFS
BFS (shift)
BFS (pop)
BFS (reassign queue)
BFS (reassign node, shift)
BFS (reassign node, pop)

Fastest: N/A

Slowest: N/A

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: one year ago)

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

Browser/OS: Chrome 104 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
DFS	59180.4 Ops/sec
BFS (shift)	91667.6 Ops/sec
BFS (pop)	74491.7 Ops/sec
BFS (reassign queue)	51293.1 Ops/sec
BFS (reassign node, shift)	89582.7 Ops/sec
BFS (reassign node, pop)	73617.0 Ops/sec

Tree Traversals (version: 0)

Comparing performance of: DFS vs BFS (shift) vs BFS (pop) vs BFS (reassign queue) vs BFS (reassign node, shift) vs BFS (reassign node, pop)

Created: one year ago by: Guest

Jump to the latest result

DFS

BFS (shift)

BFS (pop)

BFS (reassign queue)

BFS (reassign node, shift)

BFS (reassign node, pop)

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A