为什么这样写的循环比递归花费时间长很多呢

Question

写了一个二叉树，然后分别使用广度遍历和深度遍历，为什么广度遍历比深度遍历用的时间长很多呢？
遍历的次数是相同的。
初学算法，请各位指教

class Node {
  constructor (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
}

class BST {
  constructor() {
    this.root = null
    this.ordered = []
    this.times = 0
  }

  insert (data) {
    var node = new Node(data, null, null)
    if (this.root === null) {
      this.root = node
    } else {
      var current = this.root
      var parent
      while(current !== null) {
        parent = current
        if (data < current.data) {
          current = current.left
        } else if (data > current.data){
          current = current.right
        } else {
          return
        }
      }
      data < parent.data ? (parent.left = node) : (parent.right = node)
    }
  }

  inOrder(node) {
    if (node !== null) {
      this.times++
      this.inOrder(node.left)
      this.ordered.push(node.data)
      this.inOrder(node.right)
    }
  }

  // 广度优先遍历
  bfs() {
    var arr = []
    arr.push(this.root)
    while(arr.length) {
      this.times++
      var node = arr.shift()
      this.ordered.push(node.data)
      if (node.left) {
        arr.push(node.left)
      }
      if (node.right) {
        arr.push(node.right)
      }
    }
  }
}
// test 
var nums = new BST();
for (var j = 0; j < 100000; j++) {
  nums.insert(Math.floor(Math.random()*100000))
}

console.time('bfs')
nums.bfs()
console.timeEnd('bfs')
console.log(nums.times)
nums.ordered.length = 0
nums.times = 0

console.time('inorder')
nums.inOrder(nums.root);
console.timeEnd('inorder')
console.log(nums.times)

Answer 1

原因是因为js里面的push和shift操作特别费时，应该是与语言的底层实现有关，把代码改一下，不使用shift而是直接去数组中取元素，那么时间将会减少一半。bfs()代码如下：

bfs() {
    var arr = []
    arr.push(this.root)
    for (let i = 0; i < arr.length; i++) {
      this.times++
      let node = arr[i]
      this.ordered.push(node.data)
      if (node.left) {
        arr.push(node.left)
      }
      if (node.right) {
        arr.push(node.right)
      }
    }
  }