Checking whether a node is expandable
You keep track of your work so far. As you say, a node is expandable if it has a child node which you haven't visited so far. In your program, every time you reach a new node in the expansion phase, you calculate all its children (you can also do this dynamically, but let's keep things simple). As time goes on, you mark each child which has been visited. In order to know whether a node is expandable, you just check whether all its children have been marked.

Of course, you don't really need to check all children. You can keep a counter at each node that counts the number of unvisited children. The next question would be – how do I find an unvisited child. It's a nice elementary exercise finding a way to achieve this efficiently.