I did that in Cars Land in DCA this summer. Walked out of the women's and straight into the men's and I'm fully grown.
Your story (being little in the mall) reminded me of one time in JC Penney in our mall. You walk down a hall and there's a Family restroom, Women's and then Men's. The line in the Women's was long but DD and I were near the front when this little girl, maybe four, came in shaking and crying. Her dad had sent her in on her own and she'd never been in by herself. She was doing the pee pee dance so I asked if she wanted my DD to help her (DD was around 12) she said no and got in the back of the line. I told her to go ahead of us. Luckily no one was mad, we all felt so bad for her. I couldn't understand why the dad didn't just didn't take her to the family restroom if he didn't want to take her into the men's.