April 30, 2012

Binary Search Trees, how do you find maximum?

Question by Rachel Moss

I’ve been working with Binary Search Trees in my spare time, and I want to be able to delete nodes from a tree.

In order to get this to work, I need to find the maximum value. How do you go about doing that? Pseudo-code or hints would be appreciated. I’m stuck and not exactly sure how to even begin this.

Answer by Starx

A simple pseudocode would be this. It it is indepandant to binary search I think.

int maxi = 0
foreach(array as item) // or any other loop
    if item>maxi then maxi = item
April 4, 2012

How to recursively build a <select> with unknown tree depth

Question by simone

I have a MySQL table with a tree data structure. The fields are _id, name and parentId. When the record hasn’t a parent, parentId defaults as 0. This way I can build an array and then recursively print each record.

The builded array looks like this:

Array
(
    [1] => Array
        (
            [parentId] => 0
            [name] => Countries
            [_id] => 1
            [children] => Array
                (
                    [2] => Array
                        (
                            [parentId] => 1
                            [name] => America
                            [_id] => 2
                            [children] => Array
                                (
                                    [3] => Array
                                        (
                                            [parentId] => 2
                                            [name] => Canada
                                            [_id] => 3
                                            [children] => Array
                                                (
                                                    [4] => Array
                                                        (
                                                            [parentId] => 3
                                                            [name] => Ottawa
                                                            [_id] => 4
                                                        )

                                                )

                                        )

                                )

                        )

                    [5] => Array
                        (
                            [parentId] => 1
                            [name] => Asia
                            [_id] => 5
                        )

                    [6] => Array
                        (
                            [parentId] => 1
                            [name] => Europe
                            [_id] => 6
                            [children] => Array
                                (
                                    [7] => Array
                                        (
                                            [parentId] => 6
                                            [name] => Italy
                                            [_id] => 7
                                        )

                                    [11] => Array
                                        (
                                            [parentId] => 6
                                            [name] => Germany
                                            [_id] => 11
                                        )

                                    [12] => Array
                                        (
                                            [parentId] => 6
                                            [name] => France
                                            [_id] => 12
                                        )

                                )

                        )

                    [8] => Array
                        (
                            [parentId] => 1
                            [name] => Oceania
                            [_id] => 8
                        )

                )

         )

 )

Printing an unordered list <ul> is very simple with recursion. Here’s the function I use:

function toUL ($arr) {

    $html = '<ul>' . PHP_EOL;

    foreach ( $arr as $v ) {

        $html.= '<li>' . $v['name'] . '</li>' . PHP_EOL;

        if ( array_key_exists('children', $v) ) {
            $html.= toUL($v['children']);
        }

    }

    $html.= '</ul>' . PHP_EOL;

    return $html;
}

But I’m stuck at printing a <select> in a tree-structured way:

Countries
-- America
---- Canada
------ Ottawa
-- Asia
-- Europe
---- Italy
---- Germany
---- France
-- Oceania

I thought to print -- as many times as the element’s depth, but I don’t know how to calculate the depth.

My question is: is it possible to build a <select> without knowing the depth?

Thank you in advance.

Answer by Starx

Pass a parameter to count the iteration like $pass

function toUL ($arr, $pass = 0) {

    $html = '<ul>' . PHP_EOL;

    foreach ( $arr as $v ) {           

        $html.= '<li>';
        $html .= str_repeat("--", $pass); // use the $pass value to create the --
        $html .= $v['name'] . '</li>' . PHP_EOL;

        if ( array_key_exists('children', $v) ) {
            $html.= toUL($v['children'], $pass+1);
        }

    }

    $html.= '</ul>' . PHP_EOL;

    return $html;
}
...

Please fill the form - I will response as fast as I can!