What is the space complexity of DFS in terms of maximum branching factor, depth of the optimal solution and maximum tree depth? Show the necessary calculation and write a logical explanation.
Depth first search will require that the nodes be expanded all the way to the maximum tree depth first, it will therefore need to add a pointer to the stack for every level of expansion. This would indicate that the space complexity is linear in the maximum depth of the tree and independent of the branching factor.
However this depends on how you expand each node. If you need to keep the nodes expanded such that the pointer is not sufficient to retrieve where you were at a particular branch you will need to keep the information about the branch options at each level. You would not need to keep this information for the expansion of branches you have already ruled out. That would lead to the space complexity being linear in both depth and linear in the branching factor. The total space required being some constant times the product of the two.