Since we have not covered the graph in detail so far, we will keep our implementation for BFS and DFS strictly for tree structure. Also, we will use the generic tree structure we have seen in Chapter 6, Understanding and Implementing Trees, (not even binary tree). We will use the same TreeNode class to define our nodes and relationship with children. So, let's now define the Tree class with BFS functionality:

class TreeNode { 

    public $data = NULL; 
    public $children = []; 

    public function __construct(string $data = NULL) { 
      $this->data = $data; 
    } 

    public function addChildren(TreeNode $node) { 
      $this->children[] = $node; 
    } 
} 

class Tree { 

    public $root = NULL; 

    public function __construct(TreeNode $node) { 
      $this->root = $node; 
    } 

    public function BFS(TreeNode $node): SplQueue { 

      $queue = new SplQueue; 
      $visited = new SplQueue; 

      $queue->enqueue($node); 

      while (!$queue->isEmpty()) { 
          $current = $queue->dequeue(); 
          $visited->enqueue($current); 

          foreach ($current->children as $child) { 
            $queue->enqueue($child); 
          } 
      } 
    return $visited; 
    }
}

We have implemented the BFS method inside the tree class. We are taking the root node as the starting point for the breadth first search. Here, we have two queues: one for keeping the nodes that we need to visit, and one for nodes which we have visited. We are also returning the visited queue at the end of the method. Let's now imitate the tree we have seen at the beginning of the section. We want to put the data just like the tree shown in the image and also check whether the BFS actually returns our expected pattern of; : 

    $root = new TreeNode("8"); 

    $tree = new Tree($root); 

    $node1 = new TreeNode("3"); 
    $node2 = new TreeNode("10"); 
    $root->addChildren($node1); 
    $root->addChildren($node2); 

    $node3 = new TreeNode("1"); 
    $node4 = new TreeNode("6"); 
    $node5 = new TreeNode("14"); 
    $node1->addChildren($node3); 
    $node1->addChildren($node4); 
    $node2->addChildren($node5); 

    $node6 = new TreeNode("4"); 
    $node7 = new TreeNode("7"); 
    $node8 = new TreeNode("13"); 
    $node4->addChildren($node6); 
    $node4->addChildren($node7); 
    $node5->addChildren($node8); 


    $visited = $tree->BFS($tree->root); 

    while (!$visited->isEmpty()) { 
      echo $visited->dequeue()->data . "
"; 
    } 

We are building the whole tree structure here by creating nodes and attaching them to root and other nodes. Once the tree is done, we are calling the BFS method to find the full sequence of traversal. The while loop at the end is printing sequences of our visited nodes. Here is the output of the preceding code:

8
3
10
1
6
14
4
7
13

We have received our expected result. Now, if we want to search to find whether a node is there or not, we can add a simple condition check for our $current node value. If it matches, then we can return the visited queue.

The BFS has a worst complexity of O (|V| + |E|), where V is the number of vertices or nodes and E is the number of edges or connections between the nodes. For space complexity, worst case is O (|V|).