While your algorithm is correct it is very inefficient. The full array is
scanned for every element in the array. If the array contains 1,000
elements, 1,000,000 comparisons will be performed and mktree_array() will be
called 1,000 times. This is known as order n squared: O(n^2) and is about as
slow as it gets.
Oh, I see that you "have to use [a] recursive function." Is this is a
homework assignment? If not and you want to make it faster, you can speed up
the code by creating a new array first that maps from $a['nid'] => $a (the
array element) to create a hash table. Then loop over the array again and
use the hash table to find the parent of each element ($a) and add it to $a.
This will be much faster without being any more complex (exchange recursion
for two simple loops).