Naive Breadth-First Search

Implementation with lists and append

let rec nbreadth = function
  | [] -> []
  | Lf :: ts -> nbreadth ts
  | Br (v, t, u) :: ts ->
      v :: nbreadth (ts @ [t; u])
(* val nbreadth : 'a tree list -> 'a list = <fun> *)

nbreadth maintains a list of pending trees. It removes the first tree, and if it is a branch, appends its children to the end of the list.

Why this is inefficient

The expression ts @ [t; u] is the problem. @ copies its entire first argument to append two elements. At depth d, the list ts contains all remaining trees at the current depth plus subtrees already queued for the next depth - potentially hundreds or thousands of elements. Each append copies them all.

Performance evidence

On a full binary tree of depth 12 (containing 4095 labels):

Implementation	Time
nbreadth (naive, with append)	30 seconds
breadth (with queues)	0.15 seconds
Speedup	200×

For larger trees, the speedup would be even more dramatic. The naive version is O(n²) in the size of the pending list, while the queue-based version is O(n).

Why this matters

This is a classic example of how a poor choice of data structure (using append to simulate a queue) can catastrophically degrade performance. The algorithm is correct, but the implementation is wasteful. The fix is to use a proper queue data structure that supports efficient addition to the tail, which we develop next.