1. Take S.length into an int variable. To avoid recomputing it for every loop.
2. Check c.data != '\u0000' instead of checking its left and right node.
3. Take the string into char[] again to avoid calling charAt and recomputing for every character from the original string.

I agree with your use of StringBuilder instead of just printing the character out.(I just saw the editorial has the same logic)