Split the half-open array segment at its midpoint, using one entry for the root: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.
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;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 . 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]The Programming Language Oberon by Niklaus Wirth. revision 3 May 2016, sections 9.2 and 10.1, variable versus value parameters
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.