Reversing a Binary Tree is a common programming interview question.
By learning how to Reverse a Binary Tree in Python, you are working towards fundamental data structure algorithms commonly found in Computer Science degrees and across the industry.
If we take a look at the following Data Tree Image, we will notice a few common points.
binary tree simply means a tree that contains between 1 and 2 child nodes.
Each node can be represented in code as follows:
The goal of this exercise is to
reverse the order of these nodes. This is actually as simple as swapping
right nodes with one another where applicable.
To do this, we will create a function called
invertTree that will take in each node as an argument.
We first check to see if the node exists and if it does, we simply swap it’s left and right nodes with one another. Then we recursively attempt to invert each leg and finally return the node.
This is all the code that is needed to perform the inversion.
We also need to initiate the data so that we can run some tests.
The above code creates a tree as per our initial illustrations above.
How do we know if our code was successful though? We will need some way to print this tree structure out and compare it both pre and post inversion.
The above code takes in the root node of our tree, and recursively prints each left and right node if available.
Let’s test it now:
This will result in the following output, which matches the two illustrations we preempted.