Run results for: Tree Traversals (update 1)

Run details:

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: Chrome 104

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 2 years ago

Test name	Executions per second
DFS	59061.5 Ops/sec
BFS (shift)	91438.1 Ops/sec
BFS (pop)	74231.6 Ops/sec
BFS (reassign queue)	52873.3 Ops/sec
BFS (reassign node, shift)	89513.4 Ops/sec
BFS (reassign node, pop)	73658.1 Ops/sec

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() }

Run results for: Tree Traversals (update 1)

DFS

BFS (shift)

BFS (pop)

BFS (reassign queue)

BFS (reassign node, shift)

BFS (reassign node, pop)