Skip to content

How to Reverse a Binary Tree in Python

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.

Initial Binary Tree

Firstly, a 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
Code language: Python (python)

The goal of this exercise is to invert or reverse the order of these nodes. This is actually as simple as swapping left and right nodes with one another where applicable.

Inverted Binary Tree

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
Code language: Python (python)

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)
Code language: Python (python)

The above code creates a tree as per our initial illustrations above.

See also  Find the Maximum Length Difference between Lists/Arrays in Python

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)
Code language: Python (python)

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)
Code language: Python (python)

This will result in the following output, which matches the two illustrations we preempted.

1245367 1376254

Notify of
1 Comment
Oldest Most Voted
Inline Feedbacks
View all comments

[…] Learn how to beat the programming interview question on how to Reverse a Binary Tree in Python with this simple tutorial. Read more […]

Would love your thoughts, please comment.x