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:
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None
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.
def invertTree(node): if node is None: return None node.left, node.right = node.right, node.left invertTree(node.left) invertTree(node.right) return 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.
sample_tree = TreeNode(1) sample_tree.left = TreeNode(2) sample_tree.right = TreeNode(3) sample_tree.left.left = TreeNode(4) sample_tree.left.right = TreeNode(5) sample_tree.right.left = TreeNode(6) sample_tree.right.right = TreeNode(7)
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.
def printTree(node): print(node.val, end="") if node.left: printTree(node.left) if node.right: printTree(node.right)
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:
//print our initial structure printTree(sample_tree) //add a line break print() //create our inverted tree and print it inverted_tree = invertTree(sample_tree) printTree(inverted_tree)
This will result in the following output, which matches the two illustrations we preempted.