Tree Traversals

Three depth-first orders

Tree traversal means visiting every node in a systematic order. Knuth identifies three depth-first traversals, all of which process the left subtree before the right subtree. They differ only in when the node’s label is visited:

Traversal	Order	Mnemonic	Application
Preorder	Node, Left, Right	NLR	Polish notation
Inorder	Left, Node, Right	LNR	Sorted output for BSTs
Postorder	Left, Right, Node	LRN	Reverse Polish notation

Naive implementations

Each traversal converts a tree into a list of labels:

let rec preorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      [v] @ preorder t1 @ preorder t2

let rec inorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      inorder t1 @ [v] @ inorder t2

let rec postorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      postorder t1 @ postorder t2 @ [v]

Example: given a tree with root A, left child B (children D, E), right child C (children F, G):

Traversal	Result
Preorder	ABDECFG
Inorder	DBEAFCG
Postorder	DEBFGCA

Inorder on BSTs

Applying inorder to a binary search tree yields the keys in sorted order. This property is the basis of treesort: build a BST from the input, then traverse inorder to get the sorted list.

Inefficiency

All three naive traversals suffer from the same problem: repeated uses of @ (append). In the worst case (a degenerate tree), the time complexity is O(_n_²) because each @ copies its first argument. The next note shows how to fix this with accumulating parameters.