I'd say it should be like 4 or even 5 kyu, not 3.

And please someone add a mention about immutable nodes to the task description (or at least mention it in test cases output). Now it's unclear and makes people hate.

My solution successfully passed all predefined tests, but sometimes fails on some random tests (and sometimes not).

I suspect it's because there are no predefined test cases that verifies that replacement should be case-sensistive, for example, 'S' is always replaced with 'Z' and not 'z'. Random tests somtimes have that cases.