-1

I have a json file taken from geonames.org and I want to add the data from that file using php recursive foreach.

I only succeeded that I just did not understand the concept of left right depth. Depth is saved correctly.

My code is:

public function buildTree($elements, $count = 1, $depth = 0)
    {
        if (isset($elements->geonames)) {
            foreach ($elements->geonames as $element) {
                $left = $count++;

                $elementDB = new \App\Geo();

                $elementDB->id        = $element->geonameId;
                $elementDB->parent_id  = NULL;
                $elementDB->left      = $left;
                $elementDB->right     = $right;
                $elementDB->depth     = $depth;
                $elementDB->name      = $element->name;
                $elementDB->country   = $element->countryCode;
                $elementDB->level     = $element->fcode;
                $elementDB->lat       = $element->lat;
                $elementDB->long      = $element->lng;
                $elementDB->save();

                $elements = $this->getList($element->geonameId, 'element');

                if ($depth < 1) {
                    $this->buildTree($elements, $count, $depth + 1);
                }

                $right = $count++;

                echo "Added element " . $element->name . "\n";
            }
        }
    }

This should happen

4
  • And what is not working with the given code?
    – Nico Haase
    Jan 11, 2019 at 16:37
  • No, it does not work. Jan 11, 2019 at 16:45
  • What exactly does that mean? What do you expect from that code? What have you tried to debug the problem?
    – Nico Haase
    Jan 11, 2019 at 16:46
  • I've added a picture of what's going to happen. Jan 11, 2019 at 17:06

3 Answers 3

1

It seems you want to understand how it works? You use recursion to process every element. Variable $elements is a tree (or sub-tree) with nodes. Your code has to look through your tree from left to right. On every iteration you check if $elements has nodes. If $elements has (it might be ordered array or struct with fields) nodes you have to process those nodes. During every checking you detect every node if they have other children nodes or not. When you find the first (let's name it "A") node that has other children nodes you have to go into on next iteration recursion to process children nodes of current child node ("A").
enter image description here

The numbers represent the order in which the nodes are accessed in Left-Right depth algorithm.

Frankly speaking I don't understand for what you have added:

$this->buildTree($elements, $count, $depth + 1);

And it's a bad style reassignment for variable in foreach: enter image description here

May be it will be interesting for you When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

1

I'm assuming here you're making a binary search tree. Basically, a tree is a graph with a root, "regular" nodes, and leaves.

There's always one single root, at the top, which is a particular node.

Leaves don't have other nodes below, they are the "ends" of the tree.

Regular nodes have possibly two children, one smaller (on the left) and one bigger (on the right). This makes something like that:

enter image description here

As you can see, all nodes coming from the left child of the root are smaller than 8. All children on the right are bigger than 8. This way, when you search for "10", you immediatly know that you have to go through the right child of the root, no need the explore left side (that means less processing time).

1

A possible binary search tree search algorithm implementation is as follows:

function buildTree($elements, $left, $right, $needle){
    if ($left > $right) return null;
    $middle = floor(($left + $right) / 2);
    $val = $elements[$middle];
    if ($val === $needle) return $val;
    else if ($val < $needle) return buildTree($elements, $left + 1, $right, $needle);
    else if ($val > $needle) return buildTree($elements, $left, $right + 1, $needle);
}

echo buildTree([1, 2, 3, 4, 5], 0, 5, 4);

You just need to adapt this to your problem

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.