Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
A binary tree is one of the most common things found in algorithm.
It just has a lot of "relatives" - e.g. data structures that were built up on the idea of a binary tree, but with a certain intent in mind.
That is the "harder" part in binary trees or "B-Trees" (mentioned the acronym as it is commonly used).
I'd recommend to look at a practical use case of a binary tree first before trying to understand what inversion means or why inversion is useful.
A binary search tree is the easiest example.
The binary search tree is sorted - left is less or equal than… right greater or equal than.
Invert it.
Now you've changed the sort direction.
... As it was a binary search tree, which was sorted before, did you need to traverse the whole tree to invert the tree?
Nope. You knew right from the beginning that left side was less equal then and right was greater equal then.
So the inversion is just changing the traversing order.
...
These things are what makes binary trees so interesting.
They are just a representation of key value structure, sprinkle a certain order of elements or add a certain behaviour to the root -/ leaf node association and you have a lot of flexibility without the necessity to change the algorithm.
If you want a more "practical" guide, lookup red black trees for an example of introducing behaviour to root / leaf nodes.
Hope I didn't bore you to death xD -
@IntrusionCM This is helpful. I think one application that may help me get this is BSP trees. I see references to this for terrain management in games. I think it will just be an ahah that will stick when I get it.
So I see posts about an interview question/challenge of inverting a binary tree. I don't use trees very often (mainly file related or parsing server nodes), but I thought I would learn how to do this.
I saw a page that started talking about different ways to invert enough to understand that one type of inversion is swapping left and right nodes. So I stopped before they showed how.
Then I created a test program that has a tree structure and also can display a tree before and after modification. This was kind of fun.
So then I wrote the inversion function. It was less than 10 lines of code. Wtf? I thought it would be harder than this.
Then I started wondering where trees were used. So today I have been learning how they are used and why I might need one to solve a problem. One use I intuited was parsing regex or a language. Apparently it is useful there.
What I am learning is that a lot of these interview questions are really test to see if you can comprehend instructions when stressed. Or you will ask questions to clarify the task. It doesn't necessarily test your ability to solve hard problems.
One thing that perplexes me. If inverting a tree is swapping nodes left<->right, then why not leave data in place and just swap roles in the functions. Maybe I completely misunderstood what inversion means or why it would be done. I guess if this is not inverting I have the structure to try other methods now.
random