Inverting a binary tree [Interview Prep]

After spending some time thinking on how to invert a binary tree , I came up with both a recursive method, But before I explain how to invert a binary tree , I would like to explain what a binary tree is and how it functions .

A binary tree is a tree like data structure the uses two binary node , hence the world "Bi" meaning two . The two node however are usually called the right binary node and left binary node . A binary node is just a data structure that stores a value and has two pointer that points to / holds the memory location another binary tree node .

For further and in-depth explanation on binary tree , check out binary tree on wikipedia . Below, is a binary tree can represented in python code :

# A representation of a binary tree
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Here self.left holds the memory location of another binary tree to the left of the current tree , this also holds for the self.right. Now to the main discussion on this page , Inverting a binary tree or BST for short. To invert a binary tree , means to flip every left node to the right and vice versa while still keeping the original tree intact just like the image below .

There are two ways of doing this recursive and iterative methods. Let us first discuss the recursive method (i.e using a function that call themselves) . Pseudocode:

1. find a terminal case , which when the binary tree is none.
2. swap the children node on the current binary tree
3. recursively call the function on both child binary tree node on the current node

def swapNode(tree):
    tree.right, tree.left = tree.left, tree.right

def invertBinaryTreeRecursive(tree):
    if tree is None:
        return
    swapNode(tree)
    invertBinaryTreeRecursive(tree.left)
    invertBinaryTreeRecursive(tree.right)

In the above code , we wrote the terminal case then swapped the current working node children , after which we call the same function recursively on each child node

Iterative method This method is more involved i.e it uses a queue [ a data structure that follows the rule called FIFO {first in first out}] queue) to hold current node before working on the child nodes as shown below.

def invertBinaryTree(tree):
    queue = [tree]
    while len(queue):
        currentNode = queue.pop(0)
        if currentNode is None:
            continue
        swapNode(currentNode)
        queue.append(currentNode.left)
        queue.append(currentNode.right)

Quick note the above code snippet can be well understood by carefully analyzing each step in the code like a computer would . This helps one to properly understand the way the process involved .

Thank you for taking your time to read this blog . Please share if you find this topic helpful.