Invert Binary Tree Leetcode Problem 226 [Python Solution]

Welcome back, everyone!

Today, we're going to tackle a pretty easy and popular LeetCode question – inverting a binary tree.

This problem is a fantastic way to understand the fundamentals of tree traversal and recursion.

So, let's dive right in.

Problem Overview

The task at hand is quite simple: given the root of a binary tree, we need to invert the tree and return its root.

But what does "inverting a binary tree" mean?

Well, it's all about swapping the positions of the nodes in the tree.

The root remains the same, but its left and right children are swapped.

Let's look at an example:

Example 1:

Input:

4
/
2 7
/ /
1 3 6 9


Output:

4
/
7 2
/ /
9 6 3 1


As you can see, we've taken the left child (2) and the right child (7) of the root and swapped their positions.

This inversion process is applied recursively to all the subtrees as well.

Understanding Constraints

Before we dive into the solution, let's briefly discuss the constraints:

• The number of nodes in the tree is in the range [0, 100].
• The value of each node (Node.val) is between -100 and 100. Now that we have a clear understanding of the problem, let's explore different approaches to solving it.

Invert Binary Tree LeetCode Problem Solution

1. Bruteforce Approach

One way to solve this problem is by performing a depth-first search (DFS) and inverting the tree using recursion.

We'll start with the base case:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    # Base case: If the root is None, return None.

if not root:
        return None

If the root is not None, we swap the positions of its left and right children:

    # Swap the children
    root.left, root.right = root.right, root.left

Now, we make two recursive calls to invert the left and right subtrees:

    # Recursively invert the left subtree
    self.invertTree(root.left)
    
    # Recursively invert the right subtree
    self.invertTree(root.right)

Finally, we return the root:

    return root

That's it!

With this approach, we recursively invert the entire binary tree.

2. Efficient Approach with Recursive Inversion

This is an efficient approach that follows a similar recursive method as the brute-force approach.

However, we can avoid making unnecessary swaps by inverting the tree more efficiently.

Here's the Python code:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None

    # Swap the children
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

    return root

This approach optimizes the code by performing the inversion directly in the swapping step.

It's elegant and more efficient, as it reduces the number of operations.

Python Code Solution

Here's a compact Python solution for inverting a binary tree:

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

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # Efficient recursive inversion
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        
        return root

With this code, you can easily solve the Invert Binary Tree problem on LeetCode.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient approach:

• Time Complexity: We visit each node in the binary tree exactly once, making the time complexity of this solution O(N), where N is the number of nodes in the tree.

• Space Complexity: The space complexity is determined by the recursive call stack.

In the worst case, the maximum depth of the call stack is the height of the tree, making the space complexity O(H), where H is the height of the tree.

In a balanced binary tree, H is approximately log(N), while in the worst case, it can be as high as N (for a skewed tree).

Reasoning Behind Our Approach

The key insight behind the approach is to recursively invert the binary tree by swapping the positions of the children at each node.

By handling the inversion in the swapping step itself, we create an elegant and efficient solution.

This problem serves as a great introduction to depth-first search (DFS) and tree traversal techniques.

In a DFS, we explore as far as possible along a branch before backtracking.

This approach allows us to efficiently navigate the tree's structure and perform operations on each node.

Related Interview Questions By Company:

• Remove Duplicates From Sorted Array LeetCode
• Missing Number LeetCode
• Meeting Rooms LeetCode

Related Interview Questions By Difficulty:

• Count Good Nodes In Binary Tree LeetCode
• Binary Tree Level Order Traversal LeetCode
• Construct String From Binary Tree LeetCode

Related Interview Questions By Category:

• Splitting A String Into Descending Consecutive Values LeetCode
• Number Of Connected Components In An Undirected Graph LeetCode
• Word Break LeetCode

Conclusion

Congratulations!

You've learned how to solve the Invert Binary Tree problem on LeetCode.

We've explored two approaches: a bruteforce method and an efficient one that optimizes the recursive inversion.

Understanding this problem is a fantastic stepping stone for tackling more complex tree-related questions.

If you found this guide helpful, please like and engage to support the our platform.

Feel free to comment, ask questions, make suggestions, and share this content.

Learning and growing together is what makes the coding community so amazing.

If you want to practice the problem or check the details, you can find it on LeetCode here.

Happy coding, and stay curious!