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

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.

68

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(
[0] => Array(
[name] => D
[children] => Array(
[0] => Array(
[name] => G
[children] => Array(
[0] => Array(
[name] => H
[children] => NULL
)
[1] => Array(
[name] => F
[children] => NULL
)
)
)
[1] => Array(
[name] => E
[children] => Array(
[0] => Array(
[name] => A
[children] => NULL
)
[1] => Array(
[name] => C
[children] => Array(
[0] => 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.

Tuesday, June 1, 2021

57

You do not need to create 2 tables in the database for this you can maintain it like below from one table only

``````+-------+---------------+---------------------------+
|   id  |   parent_id   |           title           |
+-------+---------------+---------------------------+
|   1   |       0       |   Parent Page             |
|   2   |       1       |   Sub Page                |
|   3   |       2       |   Sub Sub Page            |
|   4   |       0       |   Another Parent Page     |
+-------+---------------+---------------------------+
``````

The array generated will be like

``````Array
(
[0] => Array
(
[id] => 1
[parent_id] => 0
[title] => Parent Page
[children] => Array
(
[0] => Array
(
[id] => 2
[parent_id] => 1
[title] => Sub Page
[children] => Array
(
[0] => Array
(
[id] => 3
[parent_id] => 1
[title] => Sub Sub Page
)
)
)
)
)
[1] => Array
(
[id] => 4
[parent_id] => 0
[title] => Another Parent Page
)
)
``````

You need to use the below recursive function to achieve it

``````function buildTree(array \$elements, \$parentId = 0) {
\$branch = array();

foreach (\$elements as \$element) {
if (\$element['parent_id'] == \$parentId) {
\$children = buildTree(\$elements, \$element['id']);
if (\$children) {
\$element['children'] = \$children;
}
\$branch[] = \$element;
}
}

return \$branch;
}

\$tree = buildTree(\$rows);
``````

The algorithm is pretty simple:

1. Take the array of all elements and the id of the current parent (initially 0/nothing/null/whatever).
2. Loop through all elements.
3. If the parent_id of an element matches the current parent id you got in 1., the element is a child of the parent. Put it in your list of current children (here: \$branch).
4. Call the function recursively with the id of the element you have just identified in 3., i.e. find all children of that element, and add them as children element.
5. Return your list of found children.
Wednesday, March 31, 2021

35

Here is an alternative solution based on the first answer and the update of the question ... :)

## Main Method

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main2 {

public static void main(String[] args) {

// input
ArrayList<Pair> pairs = new ArrayList<Pair>();
// ...

// Arrange
// String corresponds to the Id
Map<String, MegaMenuDTO> hm = new HashMap<>();

// populate a Map
for(Pair p:pairs){

//  ----- Child -----
if(hm.containsKey(p.getChildId())){
mmdChild = hm.get(p.getChildId());
}
else{
hm.put(p.getChildId(),mmdChild);
}
mmdChild.setId(p.getChildId());
mmdChild.setParentId(p.getParentId());
// no need to set ChildrenItems list because the constructor created a new empty list

// ------ Parent ----
if(hm.containsKey(p.getParentId())){
mmdParent = hm.get(p.getParentId());
}
else{
hm.put(p.getParentId(),mmdParent);
}
mmdParent.setId(p.getParentId());
mmdParent.setParentId("null");

}

// Get the root
if(mmd.getParentId().equals("null"))
}

// Print
System.out.println("DX contains "+DX.size()+" that are : "+ mmd);
}

}

}
``````

## Pair class :

``````public class Pair {
private String childId ;
private String parentId;

public Pair(String childId, String parentId) {
this.childId = childId;
this.parentId = parentId;
}
public String getChildId() {
return childId;
}
public void setChildId(String childId) {
this.childId = childId;
}
public String getParentId() {
return parentId;
}
public void setParentId(String parentId) {
this.parentId = parentId;
}

}
``````

``````import java.util.ArrayList;
import java.util.List;

private String Id;
private String name;
private String parentId;

this.Id = "";
this.name = "";
this.parentId = "";
}

public String getId() {
return Id;
}
public void setId(String id) {
Id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getParentId() {
return parentId;
}
public void setParentId(String parentId) {
this.parentId = parentId;
}
return childrenItems;
}
this.childrenItems = childrenItems;
}
if(!this.childrenItems.contains(childrenItem))
}

@Override
public String toString() {
return "MegaMenuDTO [Id=" + Id + ", name=" + name + ", parentId="
+ parentId + ", childrenItems=" + childrenItems + "]";
}

}
``````
Sunday, August 1, 2021

19
``````\$ritit = new RecursiveIteratorIterator(new RecursiveDirectoryIterator(__DIR__), RecursiveIteratorIterator::CHILD_FIRST);
\$r = array();
foreach (\$ritit as \$splFileInfo) {
\$path = \$splFileInfo->isDir()
? array(\$splFileInfo->getFilename() => array())
: array(\$splFileInfo->getFilename());

for (\$depth = \$ritit->getDepth() - 1; \$depth >= 0; \$depth--) {
\$path = array(\$ritit->getSubIterator(\$depth)->current()->getFilename() => \$path);
}
\$r = array_merge_recursive(\$r, \$path);
}

print_r(\$r);
``````
Saturday, August 14, 2021

23

from Django while loop question and

http://docs.djangoproject.com/en/dev/howto/custom-template-tags/#inclusion-tags

``````# view.py

@register.inclusion_tag('children.html')
def children_tag(person):
children = person.children.all()
return {'children': children}

# children.html

<ul>
{% for child in children %}
<li> <a href="{{ child.get_absolute_url }}">{{ child }}</a></li>
{% if child.children.count > 0 %}
{% children_tag child %}
{% endif %}
{% endfor %}
</ul>

{% children_tag parent %}

``````
Sunday, September 5, 2021