The pseudocode for DFS looks straightforward. In order to track the sequence of node visits, we need to use a queue, which will track the nodes inside our Tree class. Here is our implementation of Tree class with recursive DFS:
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 $visited;
public function __construct(TreeNode $node) {
$this->root = $node;
$this->visited = new SplQueue;
}
public function DFS(TreeNode $node) {
$this->visited->enqueue($node);
if($node->children){
foreach ($node->children as $child) {
$this->DFS($child);
}
}
}
}
As we can see, we have added one extra property in the tree class $visited to keep track of the visited nodes. When we are calling the DFS method, we are adding the node to the queue. Now, if we use the same tree structure from the previous section, and just add the DFS call and fetch the visited part, it will look like this:
try {
$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);
$tree->DFS($tree->root);
$visited = $tree->visited;
while (!$visited->isEmpty()) {
echo $visited->dequeue()->data . "
";
}
} catch (Exception $e) {
echo $e->getMessage();
}
Since DFS does not return anything, we are using the class property visited to get the queue so that we can show the sequence of visited nodes. If we run this program in console, we will have the following output:
8
3
1
6
4
7
10
14
13
The results correspond to what was expected. If we need an iterative solution for DFS, we have to remember that we need to use stack instead of queue to track the next node to visit. However, as stack follows the LIFO principle, for our mentioned graph image, the output will be different from our initial thought. Here is the implementation using the iterative approach:
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 DFS(TreeNode $node): SplQueue {
$stack = new SplStack;
$visited = new SplQueue;
$stack->push($node);
while (!$stack->isEmpty()) {
$current = $stack->pop();
$visited->enqueue($current);
foreach ($current->children as $child) {
$stack->push($child);
}
}
return $visited;
}
}
try {
$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->DFS($tree->root);
while (!$visited->isEmpty()) {
echo $visited->dequeue()->data . "
";
}
} catch (Exception $e) {
echo $e->getMessage();
}
It looks very similar to our iterative BFS algorithm. The main difference is the use of stack data structure instead of queue data structure to store the visited nodes. It will also have an impact on the output. The preceding code will produce the output 8 → 10 → 14 → 13 → 3 → 6 → 7 → 4 → 1. This is different from our previous output shown in the last section. As we are using stack, the output is actually correct. We are using stack to push the child nodes of a particular node. For our root node, which has value 8, we have the first child node with value of 3. It is pushed to the stack, and then, the second child node of root has the value of 10 and is also pushed to the stack. Since value 10 was pushed last, it will come first, following the LIFO principle of stack. So, the ordering is always going to be starting from the last branch to the first branch if we are using stack. However, if we want to keep the node ordering from left to right, then we need to make a small adjustment in our DFS code. Here is the code block with the change:
public function DFS(TreeNode $node): SplQueue {
$stack = new SplStack;
$visited = new SplQueue;
$stack->push($node);
while (!$stack->isEmpty()) {
$current = $stack->pop();
$visited->enqueue($current);
$current->children = array_reverse($current->children);
foreach ($current->children as $child) {
$stack->push($child);
}
}
return $visited;
}
The only difference from the previous code block is that we are adding the following line before visiting the child nodes from a particular node:
$current->children = array_reverse($current->children);
Since stack does the Last-In, First-Out (LIFO), by reversing, we are making sure the first node is visited first, as we reversed the order. In fact, it will simply work as a queue. This will produce the desired sequence as shown in the DFS section. If we have a binary tree, then we do it easily without requiring any reversal as we can choose to push the right child first, followed by the left child node to pop the left child first.
DFS 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, the worst case is O (|V|), which is similar to BFS.