= Solution
Split the index range at its middle:
``
def MakeTree(u: Array[Int], a: Int, b: Int): Tree = {
require(0 <= a && a <= b && b <= u.length)
if (a == b) null
else {
val middle = a + (b - a) / 2
new Tree(u(middle),
MakeTree(u, a, middle),
MakeTree(u, middle + 1, b))
}
}
``
For $N=b-a>0$, the child sizes are $\lfloor N/2\rfloor$ and $N-1-\lfloor N/2\rfloor$, differing by at most one. <Induction> gives the same property at every descendant, so \b[the result is nearly balanced]. Its inorder traversal is the initial subrange, then $u(middle)$, then the final subrange, reproducing exactly $u[a..b)$ with every occurrence retained.
There is one nonempty <recursive call> per constructed node and one constant-time base call per empty child position. Therefore construction takes \b[$\Theta(N)$ time for $N\geq1$], or $\Theta(N+1)$ including the empty case, and allocates exactly $N$ nodes. The balanced <recursion> has logarithmic stack depth. The input <array> need not be sorted: the required property concerns <subtree> sizes and inorder order, not a search-tree ordering.
Back to article page
