Router/NAT on public or private (or both) network

I'm taking a practice exam for AWS, though their VPC technology may be different than Cisco there were 2 options. One to place the NAT on the private network and one to place the NAT on the public network. Shouldn't it be on both or in the DMZ? I answered private and the correct answer was public. Then I thought the same question for a router as an Internet Gateway. Any help would be appreciated, Thanks!