4 ms·
I have yet to see a definition of what “invert a binary tree” even means.
by commandlinefan 8y ago
I have yet to see a definition of what “invert a binary tree” even means.
- nickbarnwell 8y agoI 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-invert-a-given-binary-tree https://www.quora.com/What-is-the-algorithmic-approach-to-in...
- balfirevic 8y agoThat 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.
- BearOso 8y agoInverting 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.
- boomlinde 8y agoinvert: to reverse in position, order, or relationship
- fenomas 8y agoI'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?
- peterkelly 8y agoIt's when you swap the left and right branches of every node, e.g.: def invert(node): if node is not None: left = invert(node.left) right = invert(node.right) node.left = right node.right = left return node
- aldanor 8y agoOr simply node.left, node.right = map(invert, (node.right, node.left))
- quietbritishjim 8y agoCoalescing those four lines onto one is fine, but writing: map(invert, (node.right, node.left)) is definitely not simpler than: invert(node.right), invert(node.left)
- peterkelly 8y agoIndeed - I just wanted to write it in a form that could easily be mapped to languages which don't support multiple simultaneous assignments :)