Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?
I was struggling with the same question. This is what I came up with after thinking it through.
With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and the children of these ancestors. Which translates in m*b where m is the max path length (so max number of ancestors) and b is the branching factor (number of children per ancestor).
With greedy search when you backtrack you can jump to any evaluated but unexpanded node, you passed going down on paths earlier. So the algorithm, when backtracking, can make pretty random jumps throughout the tree leaving lots of sibling nodes unexpanded. You will have to remember the value of the evaluation function for all these unexpanded nodes though because possibly they are next up when backtracking occurs. So in a theoretical very worst-case scenario that could mean that almost the whole tree needs to be remembered. Hence O(b^m).
I know there are still gaps in the reasoning but intuitively this makes me understand it best.