Leetcode – Invert Binary Tree Solution in Python

Spread the love

Introduction

Inverting a binary tree, often dubbed as the “Reverse Engineering” of trees, is an elegant and classical problem in computer science. In this extensive article, we shall unravel the Invert Binary Tree problem on LeetCode, elucidate the conceptual understanding behind binary trees, and lay down various approaches to solve this problem in Python.

Problem Statement

The Invert Binary Tree problem (LeetCode #226) is stated as follows:

Invert a binary tree.

Example: Input:

    4
   /   \
  2     7
 / \   / \
1   3 6   9

Output

    4
   /   \
  7     2
 / \   / \
9   6 3   1

This problem asks for the inversion of a binary tree, effectively mirroring it.

Prerequisites

To invert a binary tree, it’s essential to understand the structure of a binary tree node. A binary tree is made up of nodes, where each node contains a left reference, a right reference, and a data element.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Approach 1: Recursive Solution

In this approach, we will recursively swap the left and right children of all nodes in the tree.

def invertTree(root):
    if root is None:
        return None
    
    # Swap the left and right subtrees
    root.left, root.right = root.right, root.left
    
    # Invert the left and right subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    return root

This recursive approach has a time complexity of O(n), where n is the number of nodes in the tree, and a space complexity of O(h), where h is the height of the tree.

Approach 2: Iterative Solution using a Queue (Breadth-First Search)

We can also solve this problem iteratively by using a queue. We will do a level order traversal and swap the left and right children of each node.

from collections import deque

def invertTree(root):
    if root is None:
        return None
    
    queue = deque([root])
    
    while queue:
        current = queue.popleft()
        
        # Swap the left and right subtrees
        current.left, current.right = current.right, current.left
        
        # Add the left and right children to the queue
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    
    return root

This iterative approach also has a time complexity of O(n) and a space complexity of O(w), where w is the maximum width of the tree.

Approach 3: Iterative Solution using a Stack (Depth-First Search)

Another iterative approach involves using a stack. This simulates the behavior of the recursive call stack.

def invertTree(root):
    if root is None:
        return None
    
    stack = [root]
    
    while stack:
        current = stack.pop()
        
        # Swap the left and right subtrees
        current.left, current.right = current.right, current.left
        
        # Add the right and left children to the stack
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)
    
    return root

This approach has the same time complexity of O(n), but with a space complexity of O(h), similar to the recursive approach.

Testing the Solutions

Create a binary tree and pass it to the invertTree function to test the solutions.

# Creating a binary tree
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)

# Inverting the binary tree
inverted_tree = invertTree(root)

Conclusion

Inverting a binary tree is a quintessential problem in computer science that challenges one’s understanding of tree data structures and traversal algorithms. Through recursive and iterative solutions, we have explored different strategies for tackling this problem efficiently.

Leave a Reply