= Solution
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 $0\leq a\leq b\leq\operatorname{LEN}(u)$. Set $n=b-a$. For $n>0$ the child sizes are $\lfloor n/2\rfloor$ and $n-1-\lfloor n/2\rfloor$, 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> $u[a..m)$, followed by $u[m]$, followed by $u[m+1..b)$, hence precisely $u[a..b)$; no <sortedness> assumption is needed.
Exactly $n$ records are allocated. Each nonempty <recursive call> makes two child calls, so there are $2n+1$ calls including empty segments. Under constant-cost allocation and <reference parameter> passing,
$$
\boxed{T(n)=\Theta(n+1),\quad\operatorname{inorder}(t)=u[a..b),\quad t\text{ is nearly balanced}.}
$$
For positive $n$ this is proportional to $b-a$; the empty case takes constant time. The <call stack> has $O(1+\log(n+1))$ depth.
Back to article page
