Split the half-open array segment at its midpoint, using one entry for the root:
PROCEDURE MakeTree(VAR u: ARRAY OF INTEGER;
                   a, b: INTEGER): Tree;
VAR m: INTEGER; t: Tree;
BEGIN
  IF a = b THEN RETURN NIL END;
  m := a + (b-a) DIV 2;
  NEW(t);
  t.label := u[m];
  t.left := MakeTree(u, a, m);
  t.right := MakeTree(u, m+1, b);
  RETURN t
END MakeTree;
The precondition is . Set . For the child sizes are and , differing by at most one. The same construction in both subtrees proves subtree-size balance at every node. Structural induction also gives the inorder traversal , followed by , followed by , hence precisely ; no sortedness assumption is needed.
Exactly records are allocated. Each nonempty recursive call makes two child calls, so there are calls including empty segments. Under constant-cost allocation and reference parameter passing,
For positive this is proportional to ; the empty case takes constant time. The call stack has depth.
The VAR marker passes a reference parameter, so every recursive call accesses the same array without copying it. Read-only access does not make copying necessary. Under the examination's value parameter convention, omitting VAR copies the whole actual array, not merely the selected segment .
If its length is , the calls therefore cost for . For a whole-input construction, :
Copying only the shrinking segments would instead lead to , but that is a different parameter passing model from passing the same actual array on every call.
Reference parameter Created 2026-10-31 Updated 2026-11-05
A reference parameter designates the caller's actual storage. Assigning through it can change what the caller subsequently observes; passing a complete independent copy would instead change only the local copy. A value parameter containing an object reference is another case: copying that reference does not copy the referenced software object.
In Oberon, a variable parameter is marked VAR and stands for the supplied actual variable. For example, a procedure accepting VAR x: INTEGER can increment the caller's integer through x.[ref]
A read-only algorithm can use a reference parameter to avoid copying a large array, while its formal specification still prohibits writes. Reference aliasing remains relevant: two parameters can designate overlapping storage. A proof of algorithm correctness must account for the actual aliasing rules rather than assume that different parameter names denote independent values.