php - Assemble menu (tree of nodes), where only parent is known

Question

I have a menu navigation, like this:

 - Page 1
 - Page 2
   - Subpage A
   - Subpage B
   - Subpage C
 - Page 3
   - Subpage D
   - Subpage E 
     - Subsubpage I
     - Subsubpage II
 - Page 4
   - Subpage F

But the CMS I use spits out a flat tree, only displaying the parent (not which level they're on). Like so:

$orig_tree = [
  [
    'db_id' => 1,
    'name' => 'Page 1',
    'parent' => 0
  ],
  [
    'db_id' => 2,
    'name' => 'Page 2',
    'parent' => 0
  ],
    'db_id' => 3,
    'name' => 'Subpage A',
    'parent' => 2
  ],
  [
    'db_id' => 4,
    'name' => 'Subpage B',
    'parent' => 2
  ],
  [
    'db_id' => 5,
    'name' => 'Subpage C',
    'parent' => 2
  ],
  [
    'db_id' => 6,
    'name' => 'Page 3',
    'parent' => 0
  ],
  [
    'db_id' => 7,
    'name' => 'Subpage D',
    'parent' => 6
  ],
  [
    'db_id' => 8,
    'name' => 'Subpage E',
    'parent' => 6
  ],
  [
    'db_id' => 9,
    'name' => 'Subsubpage I',
    'parent' => 8
  ],
  [
    'db_id' => 10,
    'name' => 'Subsubpage II',
    'parent' => 8
  ],
  [
    'db_id' => 11,
    'name' => 'Page 4',
    'parent' => 0
  ],
  [
    'db_id' => 12,
    'name' => 'Subpage F',
    'parent' => 11
  ]
]

These information are stored in the database, so it has to be assembled in runtime (and it's really large), which means that I would like to make it as performance-friendly as possible.

So how do I put together this tree? ?

Assumptions

• I'm pretty sure that the flat original tree always will be in order. So that the first entry always will be a root node (and not one of the children of another node). And that child-nodes will come just after the parent.
• At the moment I have at most 3 levels. But it would be cool with a solution that worked with any number of levels.

---

Attempts

I'm making an object and making methods for all these operations. This is just to illustrate the solution in the fastest manner, to make the problem more digestible.

Attempt 1 - Recursion

Recursion would be the prettiest. I had a few go's at it, but I couldn't get it to work. Here is how far I made it:

  __constructor( $orig_tree ){
  $final_tree = [];
    foreach( $orig_tree as $orig_node ){
      $final_tree = $this->addNode( $orig_node, $final_tree );
    }
  } 

  private function addNode( $node, $final_tree ){
    if( $node['parent'] == 'None' ){
      $final_tree[] = $node;
    } else {
      // This is where I get stuck...
      $this->findParentNode( $node, $final_tree ); // This is wrong
    }
  }

I'm not sure, if I should work it from the root to the leaves or the other way around. Or if the final tree should be passed to the recursive method or not.

Attempt 2 - Brute Force ugly

?First assemble all the branches, and then go through the branches and assemble the tree.

public static function makeMenu( $orig_tree ){
  $branches = [];
  $final_tree = [];

  // Assemble branches
  foreach( $orig_tree as $node ){
    $branches[ $node->parent ][] = $node;
  }

  $final_tree = $branches[0]; // Set root level manually
  unset( $branches[0] );

  // Go through the root nodes and see if any branches have them as parents
  foreach( $final_tree as &$root_node ){
    if( array_key_exists( $root_node->db_id, $branches ) ){
      $root_node->children = $branches[ $root_node->db_id ];
      unset( $branches[ $root_node->db_id ] );

      // Go through the newly added children and see if they have any branches, with them as parents
      foreach( $root_node->children as &$child ){
        if( array_key_exists( $child->db_id, $branches ) ){
          $child->children = $branches[ $child->db_id ];
          unset( $branches[ $child->db_id ] );
        }
      }
    }
  }

  if( !empty( $branches ) ){
    // Throw error.
    echo 'Something has gone wrong!'; // All branches should have been removed with above code 
    die();
  }


  return $final_tree;
}

This works, but it's ugly.

Answer 1

<?php

function makeMenu( $orig_tree ){
    $parent_set = [];
    $result = [];
    foreach($orig_tree as $node){
        $node['children'] = [];
        if($node['parent'] == 0){
            $result[] = $node;
            $parent_set[$node['db_id']] = &$result[count($result) - 1];
        }else{
            $parent = &$parent_set[$node['parent']];
            $parent['children'][] = $node;
            $parent_set[$node['db_id']] = &$parent['children'][count($parent['children']) - 1];
        }
    }
    
    return $result;
}

---

In the above code, as you mentioned parent entries will always come before child entries

• We maintain a variable $result where we just add parent level 0 nodes.
• Important part is the $parent_set where we store the addresses of nodes present in $result with the help of & address specifier.
• Now, whenever we want to add any new node to $result, we fetch it's parent node from $parent_set and add current node in its children array.
• Once done, we again update current node's address in $result with the help of parent's children array entry.