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

I have an array of arrays that contains parent-child relationships between nodes in a graph. Each of the nested arrays has the form

``````array( 0 => parent_node_id, 1 => child_node_id )
```

```

So, in this array:

``````0 => array(
0 => 1
1 => 3
)
```

```

the two nodes are 1 and 3, and between node 1 and node 3 (parent-child relationship) (the index of the outer array `0`

does not matter).

``````1 => array(
0 => 3
1 => 5
),
```

```

represents the parent-child relationship between node 3 and node 5 ( `1`

doesn't matter).

Here is an array of parent-child relationships (note that the array index of the outer array (0, 1, 2, 3, etc.) does not represent anything):

``````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
)
```

```

Here is a graphical representation of the data structure it encodes: And in the code behind the code (although any ideas for the structure of the array that I can generate the HTML list later would be appreciated!):

``````0 => array
0 => 1
1 => array
0 => 3
1 => array
0 => 5
2 => array
0 => 7
3 => array
0 => 9
2 => array
0 => 10
1 => array
0 => 15
```

```

Using the information from this array, I would like to generate a tree that can then be used to create a menu in the html page. How do I do this using only my array of parent-child relationships?

I know there are many similar algorithms available on Stack Overflow, but none of them work with multiple roots or the specific array input structure that I am using.

+3

source to share

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 ][ \$a ] = '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 ] = 1; # parent node
\$c[ \$v ] = 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>
```

```
0

source

My contribution. There are only three types of elements in the array:

• elements that are PARENT
• elements that are PARENT and CHILD
• items that are CHILDREN

Based on these three rules, you can create a menu:

• Complete all elements and save parent and child by number.

``````result: 3 parents: 1, 3 and 10.
6 children: 3, 5, 7, 9, 10 and 15.
```

```
• Now we need to filter these results:

2a: SINGLE CHILD is an element of children , not parents

``````       result **real children**: 5, 7, 9, and 15 have no child of their own
```

```

2b: Get PARENT / CHILD combinations by subtracting LONIL CHILDREN from all children

``````       result **parent/child**: 3 and 10 have a parent and child(ren)
```

```

2c: Get the COMMON PARENT by subtracting PARENT / CHILD from PARENT

``````       result: **real parent** is 1
```

```

And in the code ...

``````\$arr=array(array(1,3),array(3,5),array(3,7),array(3,9),array(1,10),array(10,15));

//1. loop array and store parents and children
foreach(\$arr as \$k=>\$v){
\$P[\$v]=\$v;
\$PC[\$v]=\$v;
}
//2a: filter out the real children
\$C = array_diff_key(\$PC,\$P);
//2b: get the parent_child combinations
\$PC=array_diff_key(\$PC,\$C);
//3: Get the real parent
\$P=array_diff_key(\$P,\$PC);

//Sorting the arrays is only needed if the starting array is not ordered
ksort(\$P);
ksort(\$PC);
ksort(\$C);

// Create LONELY CHILDS
foreach(\$C as \$k=>\$v){
if(!isset(\$MC[\$v])){\$MC[\$v]=array();}
}

// Build the PARENT-CHILD menu by adding the CHILDREN to their rightfull parents
foreach(\$PC as \$k=>\$v){
if(!isset(\$MPC[\$v])){\$MPC[\$v]=array();}
}

// Create the REAL PARENT
foreach(\$P as \$k=>\$v){
if(!isset(\$MP[\$v])){\$MP[\$v]=array();}
}

foreach(\$MP as \$k=>\$v){
}

```

```

Result:

EDIT changed two lines to create valid HTML

And a new violin

0

source

All Articles