I think over-complicated and over-engineered are not the same thing.
Over-complicated is adding too many features, too much mechanism, too many moving parts. Over-engineering is far exceeding the requirements in an unhelpful way. For example: build me a treehouse. Said treehouse could probably be made of wood. If you made it out of concrete and steel, it might be a heck of a lot stronger and last a heck of a lot longer, without being more complicated (just more expensive). Too strong is over-engineered. If you made a treehouse with 13 bedrooms and an elevator, glass windows, solar power, and running water, that's overcomplicated.
I think your concrete treehouse counts too though. Add a shower and suddenly you need plumbing, drainage, the structure has to hold more weight. The overcomplicated part drags the overengineered part along with it. They pretty much collapse into the same thing.
Reminds me of the Seinfeld episode where he hires a contractor to work on his kitchen and ends up with twice as many cabinets as he had before.
I generally use: - Overbuilt: Designed to handle more of the same. Too strong. - Overengineered: Complexity not justified by the requirements.
Sometimes overbuilding (e.g. using really thick wood on a treehouse) means you can lower complexity (less bracing needed) at the cost of being more wasteful with material. That is often a great tradeoff.