Leaves are losing positions because the player whose turn it is at a leaf has already lost (no moves available, or the leaf is a terminal state by problem definition). For internal vertices, check all children.
If any child is a losing position, the current vertex is winning. Implement this with a recursive DFS. Compute the outcome for all children before computing the outcome for the parent. This bottom-up approach naturally follows the tree structure.