递归执行广度优先搜索
如果使用数组作为二叉树的后备，则可以通过代数方式确定下一个节点。如果 i 是节点，则可以在 2i + 1 中找到其左子节点，2i + 2 中找到其右子节点。除非 i 是 2 的幂次方，否则可以通过 i + 1 给出节点的下一个邻居。
下面是对使用数组作为后备的二叉搜索树执行广度优先搜索的非常天真实现的伪代码。此做法假设了有一个固定大小的数组和固定深度的树。它将查看无父节点的节点，可能会创建一个难以管理的大堆栈。
bintree-bfs(bintree, elt, i)
if (i == LENGTH)
return false
else if (bintree[i] == elt)
return true
else
return bintree-bfs(bintree, elt, i+1)
（我假设这只是一种思维练习，甚至是一个戏弄性的作业/面试问题，但我可以想象一些奇怪的情况，在某些情况下你不允许使用任何堆空间[一些真的糟糕的自定义内存管理者？一些奇怪的运行时/操作系统问题？]，但你仍然可以访问堆栈...）\n\n广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质基本上相反，所以尝试将调用堆栈（它是一种堆栈，因此被命名为堆栈）用作辅助存储（队列）基本上注定失败，除非你在处理调用堆栈时做了一些愚蠢荒谬的事情。\n\n同样，您尝试实现的任何非尾递归本质上都是将堆栈添加到算法中。这使得它不再是二叉树上的广度优先搜索，因此传统BFS的运行时间和其他方面不再完全适用。当然，您总是可以将任何循环轻松地转换为递归调用，但这不是任何有意义的递归。\n\n然而，正如其他人所证明的那样，有办法实现遵循BFS语义的算法，但代价是一些成本。如果比较的成本很高但节点遍历很便宜，那么就像@Simon Buchan所做的那样，只需运行迭代深度优先搜索，并仅处理叶子节点。这意味着不需要在堆中存储增长的队列，只需要一个本地深度变量，并且随着树的重复遍历，堆栈被一遍又一遍地建立。而像@ Patrick所指出的那样，由数组支持的二叉树通常按广度优先遍历顺序存储，因此对其进行广度优先搜索也是微不足道的，也不需要辅助队列。