undefined | Better HN

0 pointsnickbarnwell7y ago0 comments

I think "mirror" is a more intuitive description of the problem, but essentially you reverse all of the left and right subtrees. This Quora question [1] has a few different approaches listed.

[1]: https://www.quora.com/What-is-the-algorithmic-approach-to-in...

0 comments

balfirevic7y ago

That doesn't sound like "inverting". If that is what it means then it is indeed a bad name.

I always thought it means making one of the leaf nodes a root of the tree. Physically, it would look like taking one of the leaf nodes with your fingers and "hanging" the tree off of it.

BearOso7y ago

Inverting means inverting the sort order. The easy answer is to encapsulate the tree in a new structure and add a Boolean flag called “inverted,” since you’re just reinterpreting the meaning of left and right children.

What you describe is called “rotation,” and is used to rebalance.

boomlinde7y ago

invert: to reverse in position, order, or relationship

fenomas7y ago

I'm confused. Doesn't the operation described in those answers just rename each node's properties, but leave the topology of the data structure unchanged?

Meaning one could just have the code accessing the tree swap which names it accesses, and the tree would behave as "inverted" with no actual need to invert anything?

j / k navigate · click thread line to collapse