Problem of The Day: Invert Binary Tree

Problem Statement

Intuition

The idea is to invert a binary tree, swapping the left and right subtrees at each node. The intuition behind this is to reverse the hierarchical structure of the tree.

Approach

I use a recursive approach to traverse the tree. The base case checks if the current node is None, and if so, it returns. Otherwise, it recursively inverts the left and right subtrees. Additionally, I swap the left and right child nodes of the current node.

Complexity

• Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is processed once during the recursive traversal.

• Space complexity: O(h), where h is the height of the binary tree. The space complexity is determined by the maximum height of the call stack during recursion. In the worst case (skewed tree), it is O(n), and in the best case (balanced tree), it is O(log n)

Code

# Definition for a binary tree node.
# 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
        
        root.left = self.invertTree(root.left)
        root.right = self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

Editorial Solution

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        queue = collections.deque([root])
        while queue:
            current = queue.popleft()
            current.left, current.right = current.right, current.left
            
            if current.left:
                queue.append(current.left)
            
            if current.right:
                queue.append(current.right)
        
        return root