[PHP + MySQL] Building a tree view

Question

I'm a little stumped on this problem and I've been thinking about it for a while now. I have a table in my DB that holds a tasks. Each task can have a parent task by holding it's primary key in the parent_id field. I have no limit on how deep these tasks can be linked.

+-----------+-------+-----+
| Field     | Type  | Key |
+-----------+-------+-----+
| id        | int   | PRI |
| parent_id | int   | MUL |
+-------------------+-----+

A task without a parent_id is a "project" and all tasks can be grouped in task groups by sharing a parent task. I would now like to populate a HTML select box with all the descendant of the project.

Task 1
  -Task 1.1
  -Task 1.2
    -Task 1.2.1
    -Task 1.2.2
  -Task 1.3
Task 2

How can I go about this? I figure some sort of recursive function is in order but I can't seem to really figure how to go about it.

Any help would be greatly apprecaited. :)

Answer 1

I highly recommend you read this article about storing hierarchical data in a database. There are two algorithms discussed there, and depending on your needs, either one of them could be appropriate.

Adjacency List Model

This is what you currently have. Each node of the tree stores a reference to it's parent, and you can recursively determine the path to a node by selecting each level of a tree and iterating through the nodes. This is simple to implement, but the drawback is that to determine a specific path to a node, recursive queries are required. If your tree is subject to a lot of changes (ie. writes), this is a good way to go, as dynamically finding each node works well with a constantly changing tree. If it's read-heavy, you've got some overhead in the recursion.

Modified Preorder Tree Traversal

My favourite, it's a very neat algorithm. Instead of storing a reference to the parent (which you can do anyway for convenience purposes), you store a reference to the "left" and "right" nodes for each given node. The entire path to a node can be determined in a single select query, or conversely, all the children of a node. The algorithm is harder to implement, but it has performance benefits for read-heavy trees. The drawback is that each time a node is moved or added, entire branches of the tree have to be recalculated, so it may not be suitable for write-heavy data sets.

Anyway, hope that article gives you some ideas. It's a good one.

Answer 2

This is an example of how you can recursively traverse your database to set up a HTML form. It is an implementation of what zombat referees to as a "Adjacency List Model".

It uses two functions: one simply to get the "top-level" elements (projects); and one recursive, to get all the children of a given element. I then use that to populate a HTML form.

<?php
/**
 * Fetches all the projects and returns them as an array.
 * "Projects" meaning: tasks without a parent.
 * @return array
 */
function getProjects() {
    $sql = "SELECT id FROM tree WHERE parentID IS NULL";
    $result = mysql_query($sql) or die(mysql_error());
    $results = array();
    while($row = mysql_fetch_assoc($result)) {
        $results[] = $row['id'];
    }
    return $results;
}

/**
 * Fetches all tasks belonging to a specific parent.
 * Adds HTML space entities to represent the depth of each item in the tree.
 * @param int $parent_id The ID of the parent.
 * @param array $data An array containing the dat, filled in by the function.
 * @param int $current_depth Indicates the current depth of the recursion.
 * @return void
 */
function getTasks($parent_id, &$data, $current_depth=1) {
    $sql = "SELECT id FROM tree WHERE parentID = {$parent_id}";
    $result = mysql_query($sql) or die(mysql_error());
    while($row = mysql_fetch_assoc($result)) {
        $data[] = str_repeat('&nbsp;', $current_depth) . '- ' . $row['id'];
        getTasks($row['id'], $data, $current_depth + 1);
    }
}


/*
 * Fetch all the data and set it up so it can be used in the HTML
 */
mysql_connect('localhost', 'usr', 'pwd');
mysql_select_db('test');

// Get all the projects, adding a "-" as the initial value of the box.
$projects = array_merge(array('-'), getProjects());

// Fetch the tasks.
// If no project has been selected, just show a "please select"
$tasks = array();
if(isset($_GET['project']) && $_GET['project'] != '-') {
    getTasks($_GET['project'], $tasks);
}
else {
    $tasks = array('Select a project');
}

mysql_close();
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"&gt;
<html>
<head>
    <title>Tree Select Example</title>
    <meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
    <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get">
        <select name="project" onchange="this.parentNode.submit();">
            <?php
            foreach($projects as $_project) {
                $selected = ($_project == @$_GET['project']) ? ' selected' : '';
                echo "<option value=\"{$_project}\"{$selected}>{$_project}</option>";
            }
            ?>
        </select><br>
        <select name="tasks[]" multiple size="10">
            <?php
            foreach($tasks as $_task) {
                echo "<option value=\"{$_task}\">{$_task}</option>";
            }
            ?>
        </select><br>
        <input type="submit">
    </form>
    <pre><?php print_r($_GET); ?></pre>
</body>
</html>