Toggle navigation
MeasureThat.net
Create a benchmark
Tools
Feedback
FAQ
Register
Log In
Tree Traversals (update 1)
(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:
3 years ago
by:
Guest
Jump to the latest result
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.shift() 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>
Run tests (6)
Previous results
Fork
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
Latest run results:
No previous run results
This benchmark does not have any results yet. Be the first one
to run it!
Related benchmarks:
adejkas
Node Tree (with nextSibling) vs Direct Access
Tree Traversals
cloneDeep vs structuredClone
Comments
Confirm delete:
Do you really want to delete benchmark?