A binary tree is one way of preparing data, usually for sorting. Each node can have a left, right, or both, children.
A
/ \
B C
/ \
D E
“Inverting the tree” means swapping the children for each node, so that the order that the nodes are visited is reversed. Depending on whether you want to copy the tree or swap it in place then the algorithm is different. C++ provides iterators too, so providing a “order reversed” iterator can be done efficiently as well.
You’re going to have to visit every node and do at least one swap for every node, and an efficient algorithm won’t do much more than that. Bring unable to do it suggests that the student programmer doesn’t understand stacks or recursion yet, so they’ve more to learn.
This is often an exercise for beginning programmers, it’s a very simple task that’s easy to understand, but leaves enough room in the implementation to make it a good exercise.
Sometimes it’s used as a test on job applications, which is total bullshit, it isn’t a good test of someones actual skills as a software developer. Because of this it’s become a bit of a joke on the internet.
This is often an exercise for beginning programmers
And non-beginners have to weigh the skill of the interviewer to figure out whether “To invert, I’ll just keep the tree as it is” is an approach they can grasp. Enlightenment is realising that the tree is already in the perfect shape.
A binary tree is one way of preparing data, usually for sorting. Each node can have a left, right, or both, children.
A / \ B C / \ D E“Inverting the tree” means swapping the children for each node, so that the order that the nodes are visited is reversed. Depending on whether you want to copy the tree or swap it in place then the algorithm is different. C++ provides iterators too, so providing a “order reversed” iterator can be done efficiently as well.
You’re going to have to visit every node and do at least one swap for every node, and an efficient algorithm won’t do much more than that. Bring unable to do it suggests that the student programmer doesn’t understand stacks or recursion yet, so they’ve more to learn.
Important context:
This is often an exercise for beginning programmers, it’s a very simple task that’s easy to understand, but leaves enough room in the implementation to make it a good exercise.
Sometimes it’s used as a test on job applications, which is total bullshit, it isn’t a good test of someones actual skills as a software developer. Because of this it’s become a bit of a joke on the internet.
And non-beginners have to weigh the skill of the interviewer to figure out whether “To invert, I’ll just keep the tree as it is” is an approach they can grasp. Enlightenment is realising that the tree is already in the perfect shape.