The first insight here is that the structure of a binary tree is determined by the predicate used to determine which path to follow.
So, you can invert the tree by inverting the predicate -- e.g., instead of testing for a < b, test for a > b.
We don't need to change the structure of the tree at all to invert it -- we can just change how we will traverse it. :)
The second insight should be that the predicate's decisions are encoded into the choice of 'left' or 'right'.
Which means that you can invert the tree by swapping the branch labels 'left' and 'right'.
It doesn't matter what order you swap the branch labels in -- the result will be the same.
The third insight should be that you don't need to swap the branch labels -- you can just look at them backward them as you traverse the tree to look things up.
Great takeaways! I totally agree with the first two points. Do you mind expanding on "you don't need to swap the branch labels", particularly which labels we're talking about?
The first insight here is that the structure of a binary tree is determined by the predicate used to determine which path to follow.
So, you can invert the tree by inverting the predicate -- e.g., instead of testing for a < b, test for a > b.
We don't need to change the structure of the tree at all to invert it -- we can just change how we will traverse it. :)
The second insight should be that the predicate's decisions are encoded into the choice of 'left' or 'right'.
Which means that you can invert the tree by swapping the branch labels 'left' and 'right'.
It doesn't matter what order you swap the branch labels in -- the result will be the same.
The third insight should be that you don't need to swap the branch labels -- you can just look at them backward them as you traverse the tree to look things up.
Great takeaways! I totally agree with the first two points. Do you mind expanding on "you don't need to swap the branch labels", particularly which labels we're talking about?
You have two branches -- say 'left' and 'right'.
Instead of modifying the tree you can modify how you traverse it.
Where you would choose 'left', instead choose 'right'.
Where you would choose 'right', instead choose 'left'.
Ah gotcha, yes!
Sometimes you need invert the tree for 3rd party library.