LeetCode #226: Invert Binary Tree

LeetCode Solutions

https://leetcode.com/problems/invert-binary-tree/

Invert Binary Tree is a famous algorithmic problem that involves modifying a binary tree. Given a binary tree, the task is to invert it such that the left subtree becomes the right subtree and vice versa. This problem can be solved using recursion.

Here are the steps to implement the solution:

  1. Check if the root node exists. If it does not exist, return None.
  2. Swap the left and right child nodes of the root node.
  3. Recursively call the function to invert the left subtree.
  4. Recursively call the function to invert the right subtree.
  5. Return the inverted root node.

Here is the completed solution for the problem in Python:

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because each node is visited once.

The space complexity of this solution is O(h), where h is the height of the binary tree. This is because the recursive call stack can have at most h frames, where h is the height of the binary tree. In the worst case, when the binary tree is skewed, the height of the binary tree can be n, which makes the space complexity O(n).