Find element by id in tree data structure

Question

Tree sample:

           root
           / | \
          1  2  4
         /      /|\
        3      5 6 7
       / \
      13 14

I have one function, that search element in tree recursively. For example i want to find element #6

public function getChildById($root,$id){

        if (!empty($root->nodes)){
            foreach ($root->nodes as $node){

                echo $node->getId()."<br>";

                if ($node->getId()==$id){
                    //if i wrote here 'echo $node->getId(), it successful find current way and last id, but the result of that return is nothing'
                    return $node;
                }else{
                    //if i add here return , it newer find 6 elemement, it stops on 13
                    /*return*/ $this->getChildById($node, $id);  
                }

            }
        }
    }

I wrote some comments, please help me, what i'm done wrong?

Answer 1

The truth is indeed in the middle: when you do not return the value of the recursive call, you lose the information you gathered. When on the other hand you return the value of the recursive call it will not work because you will then always return in the first iteration of your foreach loop.

So, you need to sometimes return it: only when you had a match in the recursive part. If no success, you should not return and continue the foreach loop:

public function getChildById($root, $id){
    if (!empty($root->nodes)){
        foreach ($root->nodes as $node){
            if ($node->getId()==$id){
                return $node;
            } else {
                $found = $this->getChildById($node, $id);
                if ($found) return $found;
            }           
        }
    }
}   

See it run on eval.in.

Note that it is more common to have the match test on the root, so at the start of the function. It comes down to the same thing, except that if the value is on the very root you call the function with, it is also found!

public function getChildById($root, $id){
    if ($root->getId()==$id) return $root;
    foreach ($root->nodes as $node){
        $found = $this->getChildById($node, $id);
        if ($found) return $found;
    }           
}