🌲226. Invert Binary Tree

Easy | Grind 75 | August 19th Friday, 2022

Given the root of a binary tree, invert the tree, and return its root Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Example 1

Example 2

Example 3

Input: root = []
Output:[

SOLUTION

We will use a breadth-first approach to solve this problem. We will begin by adding the root node to our queue. We will then loop through the queue until it is empty. Each time we loop through the queue, we will remove the first node and check to see if it has both left and right nodes. If the left and right nodes exist, we will add them to the queue and swap them. We will repeat this process until the queue is empty. Since we will only add nodes to the queue when they exist, the queue will be empty after we have visited all of the nodes. Additionally, since the root will never be swapped, we can simply return the root, which will now contain the swapped tree.

# 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]:
        # atleast one node exist 
        if root: 
            queue = deque()
            queue.append(root)
        
            while queue:
                curr = queue.pop()

                if curr.left:
                    # add left node to the queue
                    queue.append(curr.left)
                    
                if curr.right: 
                    # add right node to queue
                    queue.append(curr.right)
                    
                # SAWP: when swapping, it doesnt matter if the nodes are null. 
                curr.left, curr.right = curr.right, curr.left

        return root

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the number of nodes. We visit every node once.

SPACE: O(n) in the worst case our queue size will be close to the number of nodes.