226: Invert Binary Tree#

Difficulty: Easy

Link to Problem: To see the Invert Binary Tree problem on LeetCode, click here!

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

# 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

def invertTree(root):
    # Base case: If the root is None or the tree is empty, return None.
    if not root:
        return None

    # Swap the left and right subtrees of the current node.
    root.left, root.right = root.right, root.left

    # Recursively invert the left and right subtrees.
    invertTree(root.left)
    invertTree(root.right)

    return root

Explanation:#

  1. We start by defining a TreeNode class, which represents a node in a binary tree. Each node has a value (val), a left child (left), and a right child (right).

  2. The invertTree function is defined to invert the binary tree. It takes the root node of the tree as an argument.

  3. In the invertTree function, we have a base case to handle the scenario when the root is None (empty tree). In such cases, we return None because there’s nothing to invert.

  4. For non-empty trees, we swap the left and right subtrees of the current node. This effectively inverts the tree at the current node.

  5. We then recursively call invertTree on the left and right subtrees to invert them.

  6. Finally, we return the root of the inverted tree.

Test cases#

### Example 1
# Input: root = [4,2,7,1,3,6,9]

root1 = TreeNode(4)
root1.left = TreeNode(2)
root1.right = TreeNode(7)
root1.left.left = TreeNode(1)
root1.left.right = TreeNode(3)
root1.right.left = TreeNode(6)
root1.right.right = TreeNode(9)

inverted_root1 = invertTree(root1)
print("Inverted Tree (Example 1):", inverted_root1)

Inverted Tree (Example 1): <__main__.TreeNode object at 0x7f30502756c0>

### Example 2
# Input: root = [2,1,3]

root2 = TreeNode(2)
root2.left = TreeNode(1)
root2.right = TreeNode(3)

inverted_root2 = invertTree(root2)
print("Inverted Tree (Example 2):", inverted_root2)

Inverted Tree (Example 2): <__main__.TreeNode object at 0x7f30502751b0>

### Example 3
# Input: root = []

root3 = None  # Empty tree

inverted_root3 = invertTree(root3)
print("Inverted Tree (Example 3):", inverted_root3)

Inverted Tree (Example 3): None

Let’s discuss the time and space complexity of the provided Python code to invert a binary tree.

Time Complexity:

The time complexity of the invertTree function is \(O(n)\), where \(n\) is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal of the tree. In the worst case, we have to visit all nodes in the tree.

The reason for this time complexity is the depth-first traversal of the tree, where we recursively process the left and right subtrees of each node.

Space Complexity:

The space complexity of the code is determined by the function call stack during the recursion. In the worst case, the space complexity is \(O(h)\), where \(h\) is the height of the binary tree.

In a completely unbalanced binary tree (essentially a linked list), the height \(h\) is equal to the number of nodes \(n\), resulting in a space complexity of \(O(n)\). This occurs when the tree is skewed to one side.

In a balanced binary tree, such as a full binary tree, the height \(h\) is \(O(log\ n)\), and the space complexity is \(O(log\ n)\).

The space complexity depends on how balanced the tree is. In practical scenarios, binary trees are often approximately balanced, so the space complexity is typically closer to \(O(log\ n)\).

In summary:

  • Time Complexity: \(O(n)\) where \(n\) is the number of nodes.

  • Space Complexity: \(O(h)\), where \(h\) is the height of the binary tree. In the worst case, it can be \(O(n)\), and in a balanced tree, it is \(O(log\ n)\).

Keep in mind that these complexities are based on the recursive implementation provided. Iterative solutions can achieve the same task with \(O(1)\) space complexity, using auxiliary data structures like stacks or queues to mimic the recursion stack.