#### [SOLVED] Convert a series of parent-child relationships into a hierarchical tree?

By Eric

I have a bunch of name-parentname pairs, that I'd like to turn into as few heirarchical tree structures as possible. So for example, these could be the pairings:

``````Child : Parent
H : G
F : G
G : D
E : D
A : E
B : C
C : E
D : NULL
``````

Which needs to be transformed into (a) heirarchical tree(s):

``````D
├── E
│   ├── A
│   │   └── B
│   └── C
└── G
├── F
└── H
``````

The end result that I want is a nested set of `<ul>` elements, with each `<li>` containing the child's name.

There are no inconsistencies in the pairings (child is it's own parent, parent is child's child, etc), so a bunch of optimizations can probably be made.

How, in PHP, would I go from an array containing child=>parent pairs, to a set of Nested `<ul>`s?

I have a feeling that recursion is involved, but I'm not quite awake enough to think it through. #### @ntt 2015-12-04 11:53:33

While Alexander-Konstantinov's solution might not seem as easy to read at first, it is both genius and exponentially better in terms of performance, this should have been voted as the best answer.

Thanks mate, I made a benchmark in your honor to compare the 2 solutions presented in this post.

I had an @250k flat tree with 6 levels that I had to convert and I was searching for a better way to do so and avoid recursive iterations.

Recursion vs Reference:

``````// Generate a 6 level flat tree
\$root = null;
\$lvl1 = 13;
\$lvl2 = 11;
\$lvl3 = 7;
\$lvl4 = 5;
\$lvl5 = 3;
\$lvl6 = 1;
\$flatTree = [];
for (\$i = 1; \$i <= 450000; \$i++) {
if (\$i % 3 == 0)  { \$lvl5 = \$i; \$flatTree[\$lvl6] = \$lvl5; continue; }
if (\$i % 5 == 0)  { \$lvl4 = \$i; \$flatTree[\$lvl5] = \$lvl4; continue; }
if (\$i % 7 == 0)  { \$lvl3 = \$i; \$flatTree[\$lvl3] = \$lvl2; continue; }
if (\$i % 11 == 0) { \$lvl2 = \$i; \$flatTree[\$lvl2] = \$lvl1; continue; }
if (\$i % 13 == 0) { \$lvl1 = \$i; \$flatTree[\$lvl1] = \$root; continue; }
\$lvl6 = \$i;
}

echo 'Array count: ', count(\$flatTree), PHP_EOL;

// Reference function
function treeByReference(\$flatTree)
{
\$flat = [];
\$tree = [];

foreach (\$flatTree as \$child => \$parent) {
if (!isset(\$flat[\$child])) {
\$flat[\$child] = [];
}
if (!empty(\$parent)) {
\$flat[\$parent][\$child] =& \$flat[\$child];
} else {
\$tree[\$child] =& \$flat[\$child];
}
}

return \$tree;
}

// Recursion function
function treeByRecursion(\$flatTree, \$root = null)
{
\$return = [];
foreach(\$flatTree as \$child => \$parent) {
if (\$parent == \$root) {
unset(\$flatTree[\$child]);
\$return[\$child] = treeByRecursion(\$flatTree, \$child);
}
}
return \$return ?: [];
}

// Benchmark reference
\$t1 = microtime(true);
\$tree = treeByReference(\$flatTree);
echo 'Reference: ', (microtime(true) - \$t1), PHP_EOL;

// Benchmark recursion
\$t2 = microtime(true);
\$tree = treeByRecursion(\$flatTree);
echo 'Recursion: ', (microtime(true) - \$t2), PHP_EOL;
``````

The output speaks for itself:

``````Array count: 255493
Reference: 0.3259289264679 (less than 0.4s)
Recursion: 6604.9865279198 (almost 2h)
`````` #### @user1364100 2014-07-24 08:04:34

How to Create Dynamic Tree View and Menu

Step 1:First we will Create treeview table in mysql database. this table contains four column.id is the task id and name is the task name.

``````-
-- Table structure for table `treeview_items`
--

CREATE TABLE IF NOT EXISTS `treeview_items` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(200) NOT NULL,
`title` varchar(200) NOT NULL,
`parent_id` varchar(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT CHARSET=latin1 AUTO_INCREMENT=7 ;

--
-- Dumping data for table `treeview_items`
--

INSERT INTO `treeview_items` (`id`, `name`, `title`, `parent_id`) VALUES
``````

Step 2: Tree view recursive method I have created below tree createTreeView() method which call recursive if current task id is greater than prev task id.

``````function createTreeView(\$array, \$currentParent, \$currLevel = 0, \$prevLevel = -1) {

foreach (\$array as \$categoryId => \$category) {

if (\$currentParent == \$category['parent_id']) {
if (\$currLevel > \$prevLevel) echo " <ol class='tree'> ";

if (\$currLevel == \$prevLevel) echo " </li> ";

echo '<li> <label for="subfolder2">'.\$category['name'].'</label> <input type="checkbox" name="subfolder2"/>';

if (\$currLevel > \$prevLevel) { \$prevLevel = \$currLevel; }

\$currLevel++;

createTreeView (\$array, \$categoryId, \$currLevel, \$prevLevel);

\$currLevel--;
}

}

if (\$currLevel == \$prevLevel) echo " </li>  </ol> ";

}
``````

Step 3: Create index file to show tree view. This is main file of treeview example here we will call createTreeView() method with required parameters.

`````` <body>
<link rel="stylesheet" type="text/css" href="_styles.css" media="screen">
<?php
mysql_connect('localhost', 'root');
mysql_select_db('test');

\$qry="SELECT * FROM treeview_items";
\$result=mysql_query(\$qry);

\$arrayCategories = array();

while(\$row = mysql_fetch_assoc(\$result)){
\$arrayCategories[\$row['id']] = array("parent_id" => \$row['parent_id'], "name" =>
\$row['name']);
}
?>
<div id="content" class="general-style1">
<?php
if(mysql_num_rows(\$result)!=0)
{
?>
<?php

createTreeView(\$arrayCategories, 0); ?>
<?php
}
?>

</div>
</body>
``````

Step 4: Create CSS file style.css Here we will write all css related class, currently I am using order list to create tree view. you can also change image path here.

``````img { border: none; }
input, select, textarea, th, td { font-size: 1em; }

/* CSS Tree menu styles */
ol.tree
{
padding: 0 0 0 30px;
width: 300px;
}
li
{
position: relative;
margin-left: -15px;
list-style: none;
}
li.file
{
margin-left: -1px !important;
}
li.file a
{
background: url(document.png) 0 0 no-repeat;
color: #fff;
text-decoration: none;
display: block;
}
li.file a[href *= '.pdf']   { background: url(document.png) 0 0 no-repeat; }
li.file a[href *= '.html']  { background: url(document.png) 0 0 no-repeat; }
li.file a[href \$= '.css']   { background: url(document.png) 0 0 no-repeat; }
li.file a[href \$= '.js']        { background: url(document.png) 0 0 no-repeat; }
li input
{
position: absolute;
left: 0;
margin-left: 0;
opacity: 0;
z-index: 2;
cursor: pointer;
height: 1em;
width: 1em;
top: 0;
}
li input + ol
{
background: url(toggle-small-expand.png) 40px 0 no-repeat;
margin: -0.938em 0 0 -44px; /* 15px */
height: 1em;
}
li input + ol > li { display: none; margin-left: -14px !important; padding-left: 1px; }
li label
{
background: url(folder-horizontal.png) 15px 1px no-repeat;
cursor: pointer;
display: block;
}

li input:checked + ol
{
background: url(toggle-small.png) 40px 5px no-repeat;
margin: -1.25em 0 0 -44px; /* 20px */
padding: 1.563em 0 0 80px;
height: auto;
}
li input:checked + ol > li { display: block; margin: 0 0 0.125em;  /* 2px */}
li input:checked + ol > li:last-child { margin: 0 0 0.063em; /* 1px */ }
``````

More Details #### @ircmaxell 2010-05-26 19:08:55

Well, first I would turn the straight array of key-value pairs into a hierarchical array

``````function convertToHeiarchical(array \$input) {
\$parents = array();
\$root = array();
\$children = array();
foreach (\$input as \$item) {
\$parents[\$item['id']] = &\$item;
if (\$item['parent_id']) {
if (!isset(\$children[\$item['parent_id']])) {
\$children[\$item['parent_id']] = array();
}
\$children[\$item['parent_id']][] = &\$item;
} else {
\$root = \$item['id'];
}
}
foreach (\$parents as \$id => &\$item) {
if (isset(\$children[\$id])) {
\$item['children'] = \$children[\$id];
} else {
\$item['children'] = array();
}
}
return \$parents[\$root];
}
``````

That'll can convert a flat array with parent_id and id into a hierarchical one:

``````\$item = array(
'id' => 'A',
'blah' => 'blah',
'children' => array(
array(
'id' => 'B',
'blah' => 'blah',
'children' => array(
array(
'id' => 'C',
'blah' => 'blah',
'children' => array(),
),
),
'id' => 'D',
'blah' => 'blah',
'children' => array(
array(
'id' => 'E',
'blah' => 'blah',
'children' => array(),
),
),
),
),
);
``````

Then, just create a rendering function:

``````function renderItem(\$item) {
\$out = "Your OUtput For Each Item Here";
\$out .= "<ul>";
foreach (\$item['children'] as \$child) {
\$out .= "<li>".renderItem(\$child)."</li>";
}
\$out .= "</ul>";
return \$out;
}
`````` #### @Tatu Ulmanen 2010-05-26 19:04:46

This requires a very basic recursive function to parse the child/parent pairs to a tree structure and another recursive function to print it out. Only one function would suffice but here's two for clarity (a combined function can be found at the end of this answer).

First initialize the array of child/parent pairs:

``````\$tree = array(
'H' => 'G',
'F' => 'G',
'G' => 'D',
'E' => 'D',
'A' => 'E',
'B' => 'C',
'C' => 'E',
'D' => null
);
``````

Then the function that parses that array into a hierarchical tree structure:

``````function parseTree(\$tree, \$root = null) {
\$return = array();
# Traverse the tree and search for direct children of the root
foreach(\$tree as \$child => \$parent) {
# A direct child is found
if(\$parent == \$root) {
# Remove item from tree (we don't need to traverse this again)
unset(\$tree[\$child]);
# Append the child into result array and parse its children
\$return[] = array(
'name' => \$child,
'children' => parseTree(\$tree, \$child)
);
}
}
return empty(\$return) ? null : \$return;
}
``````

And a function that traverses that tree to print out an unordered list:

``````function printTree(\$tree) {
if(!is_null(\$tree) && count(\$tree) > 0) {
echo '<ul>';
foreach(\$tree as \$node) {
echo '<li>'.\$node['name'];
printTree(\$node['children']);
echo '</li>';
}
echo '</ul>';
}
}
``````

And the actual usage:

``````\$result = parseTree(\$tree);
printTree(\$result);
``````

Here's the contents of `\$result`:

``````Array(
 => Array(
[name] => D
[children] => Array(
 => Array(
[name] => G
[children] => Array(
 => Array(
[name] => H
[children] => NULL
)
 => Array(
[name] => F
[children] => NULL
)
)
)
 => Array(
[name] => E
[children] => Array(
 => Array(
[name] => A
[children] => NULL
)
 => Array(
[name] => C
[children] => Array(
 => Array(
[name] => B
[children] => NULL
)
)
)
)
)
)
)
)
``````

If you want a bit more efficiency, you can combine those functions into one and reduce the number of iterations made:

``````function parseAndPrintTree(\$root, \$tree) {
\$return = array();
if(!is_null(\$tree) && count(\$tree) > 0) {
echo '<ul>';
foreach(\$tree as \$child => \$parent) {
if(\$parent == \$root) {
unset(\$tree[\$child]);
echo '<li>'.\$child;
parseAndPrintTree(\$child, \$tree);
echo '</li>';
}
}
echo '</ul>';
}
}
``````

You'll only save 8 iterations on a dataset as small as this but on bigger sets it could make a difference. #### @Enrique 2012-12-17 13:58:59

Tatu. How could I change the printTree function to not directly echo the tree's html but save all the output html into a variable and return it? thanks #### @razor7 2014-04-25 20:52:02

Hi, I think function declaration must be parseAndPrintTree(\$tree, \$root = null) and recursive call shall be parseAndPrintTree(\$child, \$tree); Best regards #### @hakre 2011-11-27 10:57:12

Another, more simplified way to convert the flat structure in the `\$tree` into a hierarchy. Only one temporary array is needed to expose it:

``````// add children to parents
\$flat = array(); # temporary array
foreach (\$tree as \$name => \$parent)
{
\$flat[\$name]['name'] = \$name; # self
if (NULL === \$parent)
{
# no parent, is root element, assign it to \$tree
\$tree = &\$flat[\$name];
}
else
{
# has parent, add self as child
\$flat[\$parent]['children'][] = &\$flat[\$name];
}
}
unset(\$flat);
``````

That's all for getting the hierarchy into a multidimensional array:

``````Array
(
[children] => Array
(
 => Array
(
[children] => Array
(
 => Array
(
[name] => H
)

 => Array
(
[name] => F
)

)

[name] => G
)

 => Array
(
[name] => E
[children] => Array
(
 => Array
(
[name] => A
)

 => Array
(
[children] => Array
(
 => Array
(
[name] => B
)

)

[name] => C
)

)

)

)

[name] => D
)
``````

The output is less trivial if you want to avoid recursion (can be a burden with large structures).

I always wanted to solve the UL/LI "dilemma" for outputting an array. The dilemma is, that each item does not know whether or not children will follow up or how many preceding elements need to be closed. In another answer I already solved that by using a `RecursiveIteratorIterator` and looking for `getDepth()` and other meta-information that my own written `Iterator` provided: Getting nested set model into a `<ul>` but hiding “closed” subtrees. That answer shows as well that with iterators you're quite flexible.

However that was a pre-sorted list, so would not be suitable for your example. Additionally I always wanted to solve this for a sort of standard tree structure and HTML's `<ul>` and `<li>` elements.

The basic concept I came up is the following:

1. `TreeNode` - Abstracts each element into a simple `TreeNode` type that can provide it's value (e.g. `Name`) and whether or not it has children.
2. `TreeNodesIterator` - A `RecursiveIterator` that is able to iterate over a set (array) of these `TreeNodes`. That is fairly simple as the `TreeNode` type already knows if it has children and which ones.
3. `RecursiveListIterator` - A `RecursiveIteratorIterator` that has all the events needed when it recursively iterate over any kind of `RecursiveIterator`:
• `beginIteration` / `endIteration` - Begin and end of the main list.
• `beginElement` / `endElement` - Begin and end of each element.
• `beginChildren` / `endChildren` - Begin and end of each children list. This `RecursiveListIterator` only provides these events in a form of function calls. children lists, as it is typical for `<ul><li>` lists, are opened and closed inside it's parent `<li>` element. Therefore the `endElement` event is fired after the according `endChildren` event. This could be changed or made configurable to broaden the use this class. The events are distributed as function calls to a decorator object then, to keep things apart.
4. `ListDecorator` - A "decorator" class that is just a receiver of the events of `RecursiveListIterator`.

I start with the main output logic. Taken the now hierarchical `\$tree` array, the final code looks like the following:

``````\$root = new TreeNode(\$tree);
\$it = new TreeNodesIterator(array(\$root));
\$rit = new RecursiveListIterator(\$it);
\$decor = new ListDecorator(\$rit);

foreach(\$rit as \$item)
{
\$inset = \$decor->inset(1);
printf("%s%s\n", \$inset, \$item->getName());
}
``````

First let's look into the `ListDecorator` that simply wraps the `<ul>` and `<li>` elements and is deciding about how the list structure is output:

``````class ListDecorator
{
private \$iterator;
public function __construct(RecursiveListIterator \$iterator)
{
\$this->iterator = \$iterator;
}
public function inset(\$add = 0)
{
return str_repeat('  ', \$this->iterator->getDepth()*2+\$add);
}
``````

The constructor takes the list iterator it's working on. `inset` is just a helper function for nice indentation of the output. The rest are just the output functions for each event:

``````    public function beginElement()
{
printf("%s<li>\n", \$this->inset());
}
public function endElement()
{
printf("%s</li>\n", \$this->inset());
}
public function beginChildren()
{
printf("%s<ul>\n", \$this->inset(-1));
}
public function endChildren()
{
printf("%s</ul>\n", \$this->inset(-1));
}
public function beginIteration()
{
printf("%s<ul>\n", \$this->inset());
}
public function endIteration()
{
printf("%s</ul>\n", \$this->inset());
}
}
``````

With these output functions in mind, this is the main output wrap-up / loop again, I go through it step by step:

``````\$root = new TreeNode(\$tree);
``````

Create the root `TreeNode` which will be used to start iteration upon:

``````\$it = new TreeNodesIterator(array(\$root));
``````

This `TreeNodesIterator` is a `RecursiveIterator` that enables recursive iteration over the single `\$root` node. It is passed as an array because that class needs something to iterate over and allows re-use with a set of children which is also an array of `TreeNode` elements.

``````\$rit = new RecursiveListIterator(\$it);
``````

This `RecursiveListIterator` is a `RecursiveIteratorIterator` that provides the said events. To make use of it, only a `ListDecorator` needs to be provided (the class above) and assigned with `addDecorator`:

``````\$decor = new ListDecorator(\$rit);
``````

Then everything is set-up to just `foreach` over it and output each node:

``````foreach(\$rit as \$item)
{
\$inset = \$decor->inset(1);
printf("%s%s\n", \$inset, \$item->getName());
}
``````

As this example shows, the whole output logic is encapsulated in the `ListDecorator` class and this single `foreach`. The whole recursive traversal has been fully encapsulated into SPL recursive iterators which provided a stacked procedure, that means internally no recursion function calls are done.

The event based `ListDecorator` allows you to modify the output specifically and to provide multiple type of lists for the same data structure. It's even possible to change the input as the array data has been encapsulated into `TreeNode`.

The full code example:

``````<?php
namespace My;

\$tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null);

// add children to parents
\$flat = array(); # temporary array
foreach (\$tree as \$name => \$parent)
{
\$flat[\$name]['name'] = \$name; # self
if (NULL === \$parent)
{
# no parent, is root element, assign it to \$tree
\$tree = &\$flat[\$name];
}
else
{
# has parent, add self as child
\$flat[\$parent]['children'][] = &\$flat[\$name];
}
}
unset(\$flat);

class TreeNode
{
protected \$data;
public function __construct(array \$element)
{
if (!isset(\$element['name']))
throw new InvalidArgumentException('Element has no name.');

if (isset(\$element['children']) && !is_array(\$element['children']))
throw new InvalidArgumentException('Element has invalid children.');

\$this->data = \$element;
}
public function getName()
{
return \$this->data['name'];
}
public function hasChildren()
{
return isset(\$this->data['children']) && count(\$this->data['children']);
}
/**
* @return array of child TreeNode elements
*/
public function getChildren()
{
\$children = \$this->hasChildren() ? \$this->data['children'] : array();
\$class = get_called_class();
foreach(\$children as &\$element)
{
\$element = new \$class(\$element);
}
unset(\$element);
return \$children;
}
}

class TreeNodesIterator implements \RecursiveIterator
{
private \$nodes;
public function __construct(array \$nodes)
{
\$this->nodes = new \ArrayIterator(\$nodes);
}
public function  getInnerIterator()
{
return \$this->nodes;
}
public function getChildren()
{
return new TreeNodesIterator(\$this->nodes->current()->getChildren());
}
public function hasChildren()
{
return \$this->nodes->current()->hasChildren();
}
public function rewind()
{
\$this->nodes->rewind();
}
public function valid()
{
return \$this->nodes->valid();
}
public function current()
{
return \$this->nodes->current();
}
public function key()
{
return \$this->nodes->key();
}
public function next()
{
return \$this->nodes->next();
}
}

class RecursiveListIterator extends \RecursiveIteratorIterator
{
private \$elements;
/**
* @var ListDecorator
*/
private \$decorator;
public function addDecorator(ListDecorator \$decorator)
{
\$this->decorator = \$decorator;
}
public function __construct(\$iterator, \$mode = \RecursiveIteratorIterator::SELF_FIRST, \$flags = 0)
{
parent::__construct(\$iterator, \$mode, \$flags);
}
private function event(\$name)
{
// event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", \$name, \$this->getDepth(), @\$this->elements[\$this->getDepth()]);
\$callback = array(\$this->decorator, \$name);
is_callable(\$callback) && call_user_func(\$callback);
}
public function beginElement()
{
\$this->event('beginElement');
}
public function beginChildren()
{
\$this->event('beginChildren');
}
public function endChildren()
{
\$this->testEndElement();
\$this->event('endChildren');
}
private function testEndElement(\$depthOffset = 0)
{
\$depth = \$this->getDepth() + \$depthOffset;
isset(\$this->elements[\$depth]) || \$this->elements[\$depth] = 0;
\$this->elements[\$depth] && \$this->event('endElement');

}
public function nextElement()
{
\$this->testEndElement();
\$this->event('{nextElement}');
\$this->event('beginElement');
\$this->elements[\$this->getDepth()] = 1;
}
public function beginIteration()
{
\$this->event('beginIteration');
}
public function endIteration()
{
\$this->testEndElement();
\$this->event('endIteration');
}
}

class ListDecorator
{
private \$iterator;
public function __construct(RecursiveListIterator \$iterator)
{
\$this->iterator = \$iterator;
}
public function inset(\$add = 0)
{
return str_repeat('  ', \$this->iterator->getDepth()*2+\$add);
}
public function beginElement()
{
printf("%s<li>\n", \$this->inset(1));
}
public function endElement()
{
printf("%s</li>\n", \$this->inset(1));
}
public function beginChildren()
{
printf("%s<ul>\n", \$this->inset());
}
public function endChildren()
{
printf("%s</ul>\n", \$this->inset());
}
public function beginIteration()
{
printf("%s<ul>\n", \$this->inset());
}
public function endIteration()
{
printf("%s</ul>\n", \$this->inset());
}
}

\$root = new TreeNode(\$tree);
\$it = new TreeNodesIterator(array(\$root));
\$rit = new RecursiveListIterator(\$it);
\$decor = new ListDecorator(\$rit);

foreach(\$rit as \$item)
{
\$inset = \$decor->inset(2);
printf("%s%s\n", \$inset, \$item->getName());
}
``````

Outpupt:

``````<ul>
<li>
D
<ul>
<li>
G
<ul>
<li>
H
</li>
<li>
F
</li>
</ul>
</li>
<li>
E
<ul>
</li>
<li>
A
</li>
<li>
C
<ul>
<li>
B
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
``````

Demo (PHP 5.2 variant)

A possible variant would be an iterator that iterates over any `RecursiveIterator` and provides an iteration over all events that can occur. An switch / case inside the foreach loop could then deal with the events.

Related: #### @Andre 2014-11-09 10:10:31

As "well engineered" as this solution is -- how exactly is it "more simplified way" than the previous examples -- It just seems like an over engineered solution to the same problem #### @hakre 2015-09-03 11:39:25

@Andre: By the grade of encapsulation IIRC. In another related answer I have a fully non-encapsulated code-fragment which is much smaller and might therefore be "more simplified" depending on POV. #### @Gangesh 2016-06-24 20:02:47

@hakre How can I modify "ListDecorator" class to add 'id' to LI, that is being fetched from tree array? #### @hakre 2016-09-23 20:27:13

@Gangesh: Most easily with a node vistor. ^^ Joking a bit, straight forward is to extend the decorator and edit beginElement(), get the inner iterator (see the inset() method for an example) and the the work with the id attribute. #### @Gangesh 2016-09-25 06:45:21

@hakre Thanks. I'll try that. #### @Alexander Konstantinov 2010-05-26 19:34:28

Yet Another Function To Make A Tree (no recursion involved, uses references instead):

``````\$array = array('H' => 'G', 'F' => 'G', ..., 'D' => null);

function to_tree(\$array)
{
\$flat = array();
\$tree = array();

foreach (\$array as \$child => \$parent) {
if (!isset(\$flat[\$child])) {
\$flat[\$child] = array();
}
if (!empty(\$parent)) {
\$flat[\$parent][\$child] =& \$flat[\$child];
} else {
\$tree[\$child] =& \$flat[\$child];
}
}

return \$tree;
}
``````

Returns an hierarchical array like this one:

``````Array(
[D] => Array(
[G] => Array(
[H] => Array()
[F] => Array()
)
...
)
)
``````

Which can easily be printed as a HTML list using recursive function. #### @Eric 2010-05-26 20:20:38

+1 - Very clever. Although I find the recursive solution more logical. But I do prefer the output format of your function. #### @vaxquis 2018-09-17 08:41:52

@Eric more logical? I beg to differ. There ain't nothing 'logical' in recursion; there's OTOH a severe cognitive overhead on parsing recursive functions/calls. If there's no explicit stack allocation, I'd take iteration over recursion every day. #### @Dan Heberden 2010-05-26 19:21:35

Here's what I came up with:

``````\$arr = array(
'H' => 'G',
'F' => 'G',
'G' => 'D',
'E' => 'D',
'A' => 'E',
'B' => 'C',
'C' => 'E',
'D' => null );

\$nested = parentChild(\$arr);
print_r(\$nested);

function parentChild(&\$arr, \$parent = false) {
if( !\$parent) { //initial call
\$rootKey = array_search( null, \$arr);
return array(\$rootKey => parentChild(\$arr, \$rootKey));
}else { // recursing through
\$keys = array_keys(\$arr, \$parent);
\$piece = array();
if(\$keys) { // found children, so handle them
if( !is_array(\$keys) ) { // only one child
\$piece = parentChild(\$arr, \$keys);
}else{ // multiple children
foreach( \$keys as \$key ){
\$piece[\$key] = parentChild(\$arr, \$key);
}
}
}else {
return \$parent; //return the main tag (no kids)
}
return \$piece; // return the array built via recursion
}
}
``````

outputs:

``````Array
(
[D] => Array
(
[G] => Array
(
[H] => H
[F] => F
)

[E] => Array
(
[A] => A
[C] => Array
(
[B] => B
)
)
)
)
`````` #### @arnorhs 2010-05-26 19:05:16

Well, to parse into ULs and LIs, it would be something like:

``````\$array = array (
'H' => 'G'
'F' => 'G'
'G' => 'D'
'E' => 'D'
'A' => 'E'
'B' => 'C'
'C' => 'E'
'D' => 'NULL'
);

recurse_uls (\$array, 'NULL');

function recurse_uls (\$array, \$parent)
{
echo '<ul>';
foreach (\$array as \$c => \$p)  {
if (\$p != \$parent) continue;
echo '<li>'.\$c.'</li>';
recurse_uls (\$array, \$c);
}
echo '</ul>';
}
``````

But I'd love to see a solution that doesn't require you to iterate through the array so often...

### Convert a inline parent-child relationships into a hierarchical tree?

• 2017-11-27 06:40:00
• Zuxriddin Kamalov
• 42 View
• 0 Score
• Tags:   php arrays

### [SOLVED] How to find a specific node in a non binary Tree?

• 2015-10-30 05:38:47
• Ryan Smith
• 3949 View
• 1 Score
• Tags:   java tree

### SQL Converting database tree structure

• 2014-01-26 10:24:19
• webrama.pl
• 74 View
• 0 Score
• Tags:   php mysql sql tree

### Php recursive function optimization

• 2011-09-30 16:53:33
• demonoid
• 373 View
• 0 Score