Breadth-First-Search in PHP

Question

My table structure is:

id    name           parent   lft  rgt
1     abc              0       2    3
2     def              1       4    5
3     geh              1       6    7
4     ijk              2       8    9
5     lmn              2       10   11

What I am doing is fetching all records first and then searching tree for all possible children using depth first search(DFS).

public function fetchRecursive($src_arr, $currentId, $parentFound = false)
{
    $cats = array();
    foreach ($src_arr as $row) {
        if ((!$parentFound && $row['id'] == $currentId) || $row['parent'] == $currentId) {
            $rowData = array();
            foreach ($row as $k => $v)
                $rowData[$k] = $v;
            $cats[] = $rowData;
            if ($row['parent'] == $currentId) {
                $cats = array_merge($cats, $this->fetchRecursive($src_arr, $row['id'], true));
            }
        }
    }
    return $cats;
}

This function is working fine and returning all children of a node.

What I am looking for is a method to get all children of a node using BFS ?

Answer 1

I wrote BFS search function myself. I used PHP's SplQueue

global variable to store array of children.

Private $queue = [];

function for BFS

public function traverseTree($rootNode, $dummyQueue) 
{
    if($rootNode->lft != 0) {
        $dummyQueue->enqueue($rootNode->lft);
    }
    if($rootNode->rgt != 0) {
        $dummyQueue->enqueue($rootNode->rgt);
    }
    if(!($dummyQueue->isEmpty())){
        $nextId = $dummyQueue->dequeue();
        $nextNode = //get next node information using $nextId
        array_push($this->queue, $nextNode);
        $this->traverseTree($nextNode, $dummyQueue);
    }
}

Call traverseTree() function

$dummyQueue = new \SplQueue();
$this->traverseTree($id, $dummyQueue);

Here $id is root node for which you want to fetch all the children.

I have also added a file in gist, suggestions and improvement are welcomed.