Is there anyone knows what is the space complexity for BFS and DFS solutions for this question? when there are recursive calls and stacks involved, I don't understand how the program actually executed. Thank you!

```
public class Solution {
public void solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++){
if ((i == 0 || i == board.length-1 || j == 0 || j == board[i].length-1) && (board[i][j] == 'O')){
dfs(i, j, board);
}
}
}
for(int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
else if (board[i][j] == 'M') {
board[i][j] = 'O';
}
}
}
}
public void dfs(int i, int j, char[][] board){
if ((i >= 0 && i < board.length && j >= 0 && j < board[i].length) && (board[i][j] == 'O')){
board[i][j] = 'M';
// the next four lines are cases where the cell is at the edge,
// in these cases we only need to check one direction,
// "in-bound" direction, to avoid unnecessary calls to dfs()
if(i == 0) dfs(i+1, j, board);
else if (j == 0) dfs(i, j+1, board);
else if(i == board.length-1) dfs(i-1, j, board);
else if(j == board[i].length-1) dfs(i, j-1, board);
else{
dfs(i-1, j, board);
dfs(i+1, j, board);
dfs(i, j-1, board);
dfs(i, j+1, board);
}
}
}
}
```