PHP Tree Maker

tree_maker.php

# input array
# hideous format: [ [ 0 => parent_node_id, 1 => child_node_id ], [ 0 => parent_node_id, 1 => child_node_id ], ... ]
$array = [
  [ 0 => 1,
    1 => 3
  ],
  [ 0 => 3,
    1 => 5
  ],
  [ 0 => 3,
    1 => 7
  ],
  [ 0 => 3,
    1 => 9
  ],
  [ 0 => 1,
    1 => 10
  ],
  [ 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 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 (aray_keys($p) as $k) {
    if (! isset($c[$k]) ) {
      $r[$k] = 1;
    }
  }
  return $r;
}