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.

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

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.

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.

1245367
1376254