function itree = pruefer_to_tree_2 ( nnode, iarray )

%*****************************************************************************80
%
%% pruefer_to_tree_2() produces the edge list of a tree from its Pruefer code.
%
%  Discussion:
%
%    One can thus exhibit all trees on N nodes, produce
%    one at random, find the M-th one on the list, etc, by
%    manipulating the Pruefer codes.
%
%    For every labeled tree on N nodes, there is a unique N-2 tuple
%    of integers A1 through AN-2, with each A between 1 and N.  There
%    are N^(N-2) such sequences, and each one is associated with exactly
%    one tree.
%
%    This routine apparently assumes that the Pruefer code is
%    generated by taking the LOWEST labeled terminal node each time.
%    This is not consistent with PRUEFER_TO_TREE and TREE_TO_PRUEFER.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    28 June 2013
%
%  Author:
%
%    Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf.
%    This version by John Burkardt.
%
%  Reference:
%
%    Albert Nijenhuis. Herbert Wilf,
%    Combinatorial Algorithms,
%    Academic Press, 1978, second edition,
%    ISBN 0-12-519260-6.
%
%  Parameters:
%
%    Input, integer NNODE, number of nodes in desired tree.
%
%    Input, integer IARRAY(NNODE).  IARRAY(I), I = 1, NNODE-2 
%    is the Pruefer code for the tree.
%
%    Output, integer ITREE(NNODE); the I-th edge of the tree
%    joins nodes I and ITREE(I).
%
  itree(1:nnode) = 0;
 
  for i = nnode-2 : -1 : 1
 
    l = iarray(i);
 
    if ( itree(l) == 0 )
      iarray(i) = - l;
      itree(l) = - 1;
    end
 
  end
 
  iarray(nnode-1) = nnode;
%
%  Find next index K so that ITREE(K) is 0.
%
  k = 1;
  j = 0;
 
  while ( itree(k) ~= 0 )
    k = k + 1;
  end
 
  kp = k;
 
  while ( 1 )
 
    j = j + 1;
    ir = abs ( iarray(j) );
    itree(kp) = ir;
 
    if ( j == nnode - 1 )
      break
    end
 
    if ( 0 < iarray(j) )
      while ( itree(k) ~= 0 )
        k = k + 1;
      end
      kp = k;
      continue
    end
 
    if ( k < ir )
      itree(ir) = 0;
      while ( itree(k) ~= 0 )
        k = k + 1;
      end
      kp = k;
      continue
    end
 
    kp = ir;

  end
%
%  Restore the signs of IARRAY.
%
  iarray(1:nnode-2) = abs ( iarray(1:nnode-2) );
 
  return
end
