I'm not sure about your breadth-first approach to read input. You should just initialize your array of length n with left and right child.

About the time, if you practice more, you will see that you can solve problems faster and faster! This one took me 10 minutes :).