PHP recursion help needed to create a tree structure

Question

Here is a table structure I have:

CREATE TABLE menu (
  menuid int(11) NOT NULL AUTO_INCREMENT,
  menuname varchar(100) NOT NULL DEFAULT '',
  menulink varchar(100) NOT NULL DEFAULT '',
  menuparentId int(11) NOT NULL DEFAULT '0',
  menuhasChild smallint(1) NOT NULL DEFAULT '0',
  menustatus smallint(1) NOT NULL DEFAULT '1',
  menuorder int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (menuid)
)

I am using a recursive function to create a menu structure from this and fail here:

function categoriesTree($id=0){    
    $s = "SELECT * FROM menu  WHERE menuparentId = '".$id."' 
        ORDER BY menuorder, menuid ";
    $rid = $this->db->query($s)->result_array();
    $treeArray = array();
    foreach($rid as $row){
        $treeArray[$row['menuid']] = $row;
        if($row['menuhasChild']==1){
            $treeArray[$row['menuid']] = $this->categoriesTree(); //results in Fatal error: Maximum function nesting level of '100' reached, aborting!
        }
    }
 retrun $treeArray;
 }

This method is part of a model in CodeIgniter model class. Is there a better way to create the tree?

I think you have to add the id as parameter in you function call: $this->categoriesTree($row['menuid']) I guess. Otherwise you call the function exactly the same every time. — mjspier
– mjspier, Commented May 11, 2011 at 8:37
d'oh, thanks for pointing, post this as an answer and I will select it, how could I miss it? I need coffee — Kumar
– Kumar, Commented May 11, 2011 at 8:57

Evert · Accepted Answer · 2011-05-11 08:34:35Z

4

Yes, there's a much better way. The so-called modified pre-order tree traversal algorithm. You can find plenty of information by googling this, and I'm sure on stack overflow as well.

The benefits are that you can fetch an entire subtree using just 1 query. SELECTS will be fast, but modifications are heavier.

answered May 11, 2011 at 8:34

Evert

101k18 gold badges136 silver badges221 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Kumar Over a year ago

evert forgive me for my naiveness, and stupidity but I never heard about this, if I had read about it in a text I have missed it like many other things

user212218 Over a year ago

Sometimes also known as nested sets.

mjspier · Accepted Answer · 2011-05-11 09:16:38Z

2

I think you have to add the id as parameter in your function call.

$this->categoriesTree($row['menuid'])

Otherwise you call the function exactly the same every time.

answered May 11, 2011 at 9:16

mjspier

6,5565 gold badges35 silver badges47 bronze badges

Comments

Krishna Karki · Accepted Answer · 2011-11-15 10:42:37Z

1

Here is the best example.. This is the corrected form of first answer.

 function categoriesTree($id=0) {
    $s = "SELECT * FROM design_menu  WHERE menuparentId = '" . $id . "' 
    ORDER BY menuorder, menuid ";
    $rid = $this->db->query($s)->result_array();
    $treeArray = array();

    foreach ($rid as $row) {

        $treeArray[$row['menuid']] = $row;
        if ($row['menuhasChild'] == 1) {
            $treeArray[$row['menuname']] = $this->categoriesTree($row['menuid']); //results in Fatal error: Maximum function nesting level of '100' reached, aborting!
        }
    }
    return $treeArray;
}

answered Nov 15, 2011 at 10:42

Krishna Karki

1,3324 gold badges14 silver badges32 bronze badges

Comments

Toto · Accepted Answer · 2011-05-11 08:56:31Z

0

The line :

$treeArray[$row['menuid']] = $this->categoriesTree();

must be :

$treeArray[$row['menuid']] = $this->categoriesTree($row['menuid']);

answered May 11, 2011 at 8:56

Toto

91.7k63 gold badges97 silver badges135 bronze badges

Comments

Roshan Wijesena · Accepted Answer · 2011-05-11 09:29:12Z

<?php
require_once ROOT_PATH . '/lib/dao/MySQLClass.php';
require_once ROOT_PATH . '/lib/confs/Conf.php';
/**
 * Generate HTML for multi-dimensional menu from MySQL database
 * with ONE QUERY and WITHOUT RECURSION
 * @author J. Bruni
 */
//print_r($_SESSION['symfony/user/sfUser/culture']);die;
class MenuBuilder
{
    /**
     * MySQL connection
     */
    var $conn;

    /**
     * Menu items
     */
    var $items = array();

    /**
     * HTML contents
     */
    var $html  = array();

        //var $culture = $_SESSION['symfony/user/sfUser/culture'];
        var $culture;
        var $columnName;
    /**
     * Create MySQL connection
     */
    function MenuBuilder()
    {
        $conf = new Conf();
            $db=new MySQLClass($conf);
           $this->conn = mysql_connect($db->myHost .':'.$db->myHostPort, $db->userName, $db->userPassword);

           $this->culture=$_SESSION['language'];

    }

    /**
     * Perform MySQL query and return all results
     */
    function fetch_assoc_all( $sql )
    {
                if($this->culture=="en"){
                $this->columnName='sm_mnuitem_name';

                }else{
                    $this->columnName='sm_mnuitem_name_'.$this->culture;
                }
                //die(print_r($_SESSION));
                if($_SESSION['user']=="USR001"){
                $query="SELECT sm_mnuitem_id, sm_mnuitem_parent, ".$this->columnName.", sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY sm_mnuitem_parent, sm_mnuitem_position;";
                }
                else{
                    $query="select * from hs_hr_sm_mnuitem m left join hs_hr_sm_mnucapability c on m.sm_mnuitem_id=c.sm_mnuitem_id left join hs_hr_users u on u.sm_capability_id=c.sm_capability_id where u.id='".$_SESSION['user']."' ORDER BY m.sm_mnuitem_parent, m.sm_mnuitem_position;";
                }
        //$result = mysql_query("SELECT sm_mnuitem_id, sm_mnuitem_parent, ".$this->columnName.", sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY sm_mnuitem_parent, sm_mnuitem_position;",$this->conn);
                $result = mysql_query($query,$this->conn);

        if ( !$result ){

            return false;

                }

        $assoc_all = array();

        while( $fetch = mysql_fetch_assoc( $result ) ){
            $assoc_all[] = $fetch;
                }
                //die(print_r($assoc_all));
        mysql_free_result( $result );

        return $assoc_all;

    }

    /**
     * Get all menu items from database
     */
    function get_menu_items()
    {
        // Change the field names and the table name in the query below to match tour needs
        $sql = 'SELECT sm_mnuitem_id, sm_mnuitem_parent, sm_mnuitem_name, sm_mnuitem_webpage_url, sm_mnuitem_position FROM hs_hr_sm_mnuitem ORDER BY s_mnuitem_parent, sm_mnuitem_position;';

        return $this->fetch_assoc_all( $sql );
    }

    /**
     * Build the HTML for the menu
     */
    function get_menu_html( $root_id = 0 )
    {
        $this->html  = array();
        $this->items = $this->get_menu_items();
                //print_r($this->items);die("");

        foreach ( $this->items as $item )
            $children[$item['sm_mnuitem_parent']][] = $item;

        // loop will be false if the root has no children (i.e., an empty menu!)
        $loop = !empty( $children[$root_id] );

        // initializing $parent as the root
        $parent = $root_id;
        $parent_stack = array();

        // HTML wrapper for the menu (open)
                //$this->html[] = '<div>';
        $this->html[] = '<ul id="qm0" class="qmmc">';

        while ( $loop && ( ( $option = each( $children[$parent] ) ) || ( $parent > $root_id ) ) )
        {
            if ( $option === false )
            {
                $parent = array_pop( $parent_stack );

                // HTML for menu item containing childrens (close)
                $this->html[] = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 ) . '</ul>';
                $this->html[] = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ) . '</li>';
            }
            elseif ( !empty( $children[$option['value']['sm_mnuitem_id']] ) )
            {
                $tab = str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 );

                // HTML for menu item containing childrens (open)
                $url="";
                if($option['value']['sm_mnuitem_webpage_url']=="#"){
                    $url="javascript:void(0);";
                }else{
                    $url=$option['value']['sm_mnuitem_webpage_url'];
                }        

                $this->html[] = sprintf(
                    '%1$s<li><a class="qmparent" href="%2$s">%3$s</a>',
                    $tab,   // %1$s = tabulation
                    //$option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $url,
                    $option['value'][$this->columnName]   // %3$s = title
                );
                $this->html[] = $tab . "\t" . '<ul>';

                array_push( $parent_stack, $option['value']['sm_mnuitem_parent'] );
                $parent = $option['value']['sm_mnuitem_id'];
            }
            else{

                // HTML for menu item with no children (aka "leaf")
                             if($_SESSION['user']!="USR001"){
                            if($option['value']['sm_mnuitem_webpage_url']!="#"){

                $this->html[] = sprintf(
                    '%1$s<li><a target="rightMenu" href="%2$s">%3$s</a></li>',
                    str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ),   // %1$s = tabulation
                    $option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $option['value'][$this->columnName]   // %3$s = title
                );
                            }
                             }else{
                                 $this->html[] = sprintf(
                    '%1$s<li><a target="rightMenu" href="%2$s">%3$s</a></li>',
                    str_repeat( "\t", ( count( $parent_stack ) + 1 ) * 2 - 1 ),   // %1$s = tabulation
                    $option['value']['sm_mnuitem_webpage_url'],   // %2$s = link (URL)
                    $option['value'][$this->columnName]   // %3$s = title
                );
                             }
                        }
        }

        // HTML wrapper for the menu (close)
        $this->html[] = '</ul>';
                //$this->html[] = '</div>';

        return implode( "\r\n", $this->html );
    }
}





?>

MikeMurko · Accepted Answer · 2011-11-15 15:56:59Z

Building a menu using tree structures with parent/child relationships based in a relational database is very cumbersome. Relational databases are terrible for tree structures. They require you to write a lot of business logic just to represent your data in a readable format. To update the menu with additional functionality requires adding to that recursive loop ... it can get really hairy depending on how complex you want your menu to become. Not to mention you will eventually want to cache the whole thing because the loop becomes quite expensive computationally under heavy loads. Think about it, if you have 5 top level menu items, 2 childs and each child having n children themselves you will be running 16 SQL statements.

May I offer another solution: JSON. I used to have a menu table like this, and now I just store a JSON representation of it in the SQL database (although even this could be cached in memory/filesystem). The JSON menu is far more compact in terms of space, it is logical to simply read and doesn't require fiddling with parent and child IDs. It works much better with PHP (json_encode/decode) turning the menu into a native array. As well as with Javascript which is important if, for example, you are doing ajax calls to reorder your menu in your application. Hierarchical tree structures are what JSON is good at. It also removes the need to keep track of your "menuorder" (because the array order is specified intrinsically)

An example menu format is as follows:

{
["en": "Home", "fr": "Accueil"],
["en": "Settings", "fr": "Paramètres", "child": 
    {
        ["en": "Email", "fr": "Email", "role": "EmailUser"]
    }
}

As you can see it offers additional functionality really easily such as a "role" tied to a menu item. Adding this kind of functionality doesn't require new recursive code, or changes to your SQL schema. It's really much more flexible.

So, not really answering the question, but hopefully providing some advice/insight into what I feel is a better solution for this problem.

Collectives™ on Stack Overflow

PHP recursion help needed to create a tree structure

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related