Tree traversal is a general concept of visiting the nodes in a tree data structure -- it is not specific to JavaScript nor otherwise strongly associated with JavaScript.

Tree data structures and tree traversal are very often used in a multitude of different software written in a multitude of different languages using a multitude of different frameworks, so it sounds rather strange when you are calling it a "Javascript concept".

Since for the char replacement it is not really relevant in which order the nodes/HTML elements are visited, i guess it's up to you to choose a traversal strategy of your liking. And, performance considerations not withstanding, there is also the querySelectAll function which you could use to get all elements in the HTML document without requiring to write code for the DOM traversal, so depending on what you actually want to learn/practice, this function might (or might not) be a suitable option for realizing a solution to your task...

[...] how would you prefer to do so if asked by a client?

That's not how this would happen in the real world. But anyway, i would do it in a way where i have (A) confidence that i will end up with a working and robust solution and (B) where have a good understanding of how much effort it will take me to implement, test, and (if required) later to maintain and update it in case the client's requirements change. And not to forget, risk management: There is always coming a point in the span of a contract project where the client (or sometimes you) realize that the requirements and functionality agreed upon are not what the client actually wants/needs or that the deliverable is incompletely specified, so you need to be able to adjust and adapt regardless of whatever "bullet-proof" implementation plan you had at the beginning of the project...

Or, you know, you can do it like it often happens in business. You just bullshit your client, even if you can't write proper production code if your life depended on it. Being a (very) good salesman can compensate for such shortcomings more than enough. I.e., the time-tested "if you can't dazzle them with brilliance, baffle them with bullshit" tactic. It works, at least in the short term...