Create a tree structure from a set of parent-child relationships

The OP's statement states that this will be used to create a menu system, so I wrote code that converts an array of arrays to a more readable data structure, builds a nested list (suitable for use as a menu), and populates the list items with data from the second array $content

. In fact, the data in $content

can be a collection of links or whatever.

# input array
$array = array(
0 => array(
   0 => 1,
   1 => 3
),
1 => array(
   0 => 3,
   1 => 5
),
2 => array(
   0 => 3,
   1 => 7
),
3 => array(
   0 => 3,
   1 => 9
),
4 => array(
   0 => 1,
   1 => 10
),
5 => array(
   0 => 10,
   1 => 15
));

# associative array of node IDs and the node contents
# obviously for a menu, the node contents will probably be links
$content = array(
  1 => 'ape',
  3 => 'bear',
  5 => 'cow',
  7 => 'dog',
  9 => 'elephant',
  10 => 'frog',
  15 => 'giraffe'
);

$tree = [];

# simplify the parent-child 
foreach (array_values($array) as $a) {
  $tree[ $a[0] ][ $a[1] ] = 'value';
}

$roots = get_root($array);

# start our initial list...    
$str = '<ul>';
foreach (array_keys($roots) as $r) {
  $str .= build_tree( $tree, $content, $r );
}
$str .= "</ul>";
echo $str;

/**
 * build_tree($tree, $content, $n)
 * 
 * builds an html representation of a tree using $tree, a data structure
 * containing parent-child relationships, $content, the content of each
 * node of the tree, and $n, the current node in the tree. Calls itself
 * recursively when it encounters a subtree to be built
 *
 * @param array $tree 
 * @param array $content - assoc array of 
 * @param string $n - current node in the tree
 * @return string $html representing the tree
 */
function build_tree($tree, $content, $n) {
  $html = "<li>node id: $n; ".$content[$n]."</li>";
  # does $n exist in $tree -- i.e. does it have a child?
  if ( isset($tree[$n]) ) {
    # if so, start a new nested list
    $html .= '<li><ul>';
    # for each of the children of $n, our parent node,
    # run the build_tree code to create the html
    foreach (array_keys($tree[$n]) as $node) {
      $html .= build_tree($tree, $content, $node);
    }
    $html .= '</ul></li>';
  }
  return $html;
}

/**
 * get_root ( $input )
 *
 * input array format:
 * 0 => [ 0 => parent_node_id, 1 => child_node_id ],
 * 1 => [ 0 => parent_node_id2, 1 => child_node_id2 ],;
 *
 * takes an associative array of parent-child relationships
 * and makes two arrays, one containing all the parent nodes,
 * and one containing the child nodes. The root nodes are
 * those that appear in the parent node array but not the
 * child node array.
 *
 * @param array $input 
 * @return array $r - assoc arr. with root nodes as keys
 */
function get_root ($input) {
  $p = [];
  $c = [];
  $r = [];
  foreach ($input as $k => $v) {
    $p[ $v[0] ] = 1; # parent node
    $c[ $v[1] ] = 1; # child node
  }
  # find the array items in $p that aren't in $c
  foreach ($p as $k => $v) {
    if (! isset($c[$k]) ) {
      $r[$k] = 1;
    }
  }
  return $r;
}

      

        
        
        
      

    

Results of the above code ( test it with this online demo ):

•   
• Node ID: 1; Content: ape  
•   
  •       
  • Node ID: 3; content: bear      
  •       
    •           
    • Node ID: 5; content: cow          
    • Node ID: 7; content: dog          
    • Node ID: 9; content: elephant      
                
  • Node ID: 10; content: frog      
  •       
    •           
    • Node ID: 15; content: giraffe      
            
    

Raw HTML (using HTML code):

<ul>
    <li>Node ID: 1; content: ape</li>
    <li>
      <ul>
        <li>Node ID: 3; content: bear</li>
        <li>
          <ul>
            <li>Node ID: 5; content: cow</li>
            <li>Node ID: 7; content: dog</li>
            <li>Node ID: 9; content: elephant</li>
          </ul>
        </li>
        <li>Node ID: 10; content: frog</li>
        <li>
          <ul>
            <li>Node ID: 15; content: giraffe</li>
          </ul>
        </li>
      </ul>
    </li>
</ul>