Efficient Tree Traversal

The problem with append

The naive traversal functions use @ in recursive calls. In a degenerate (unbalanced) tree, this leads to O(_n_²) total time because each append copies the left result. The fix follows the same pattern used throughout the course: introduce an accumulating parameter to eliminate @.

Efficient versions

Each function takes a pair (tree, accumulator), where the accumulator vs collects the result:

let rec preord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      v :: preord (t1, preord (t2, vs))

let rec inord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      inord (t1, v::inord (t2, vs))

let rec postord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      postord (t1, postord (t2, v::vs))

All three are O(n) in time for a tree of size n. They use cons (::) instead of append (@), a classic example of reduction in strength: replacing an expensive operation with a series of cheap ones.

Relating efficient and naive versions

The efficient versions satisfy equations that connect them to the naive ones. For example:

inord(t, vs) = inorder(t) @ vs

This identity means that inord computes the same result as the naive inorder followed by append, but does so in linear time rather than quadratic.

All three are depth-first

Preorder, inorder, and postorder are all depth-first traversals: each traverses the entire left subtree before touching the right subtree. An alternative is breadth-first traversal, which visits nodes level by level, covered in the Queues lecture.