Return replacing nodes in traverse()

This represents the first steps in refactoring towards
immutability of big parts of nodes and more efficient
copying of nodes (#13640).

Change-Id: I00845d1470e71a8cb1ae32cc9851e4f3ec1a734e