minimax for isolation game, more like DFS or BFS?

This is in relation to the Udacity Georgia Tech lectures on a game called isolation where you draw X’s and O’s on the board until one player runs out of spaces to move to.

Regardless of the game, I am given a depth=4, but the branching factor is 64 at most at each level since in the version of isolation I am working on, players can move one space left or right or up or down and each side has 3 queens to move on every turn.

My question is, do I work all the way to depth=4 along a particular chain of branches, sort of like DFS (depth-first), then bubble up the utility from my evaluation function to the top level move that lead there or do I save the game states level by level sort of like BFS (breadth-first) to depth=4 then run the evaluation function on all the bottom game states?

Right now, I am working on the latter version (more like BFS) but it seems like it may not have the best time complexity nor space complexity. The next part of the assignment is to implement alpha-beta pruning and finally iterative deepening.