algoadvance

The problem “Invert Binary Tree” asks you to invert a given binary tree. An inverted (or mirrored) binary tree is one where the left and right children of all nodes are swapped.

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

Example:

Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Clarifying Questions

  1. What is the structure of the tree node?
    • The tree node has three attributes: val, left, and right.
  2. Are there any constraints in terms of tree size?
    • Yes, the number of nodes in the tree is in the range [0, 100].
    • The value of each node is in the range [-100, 100].
  3. Should we handle non-binary tree cases?
    • No, we are only dealing with binary trees.
  4. What should be returned if the tree is empty (i.e., root is None)?
    • If the root is None, we should return None.

Strategy

To solve this problem, we can use a recursive approach:

  1. Base Case:
    • If the current node is None, return None because there’s nothing to invert.
  2. Recursive Case:
    • Swap the left and right children of the current node.
    • Recursively invert the left subtree.
    • Recursively invert the right subtree.

An iterative approach using a queue (BFS) or stack (DFS) can also accomplish this task, but the recursive method is straightforward and easy to implement for binary tree problems.

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

def invertTree(root: TreeNode) -> TreeNode:
    # Base case: if the root is None, return None
    if root is None:
        return None
    
    # Swap the left and right children
    root.left, root.right = root.right, root.left
    
    # Recursively invert both subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    return root

Time Complexity

The time complexity of this approach is (O(n)), where (n) is the number of nodes in the tree. This is because in the worst-case scenario, we need to visit every node once to invert the tree.

The space complexity is (O(h)), where (h) is the height of the tree, due to the recursion stack. In the worst case, (h) could be (O(n)) for a skewed tree, making the worst-case space complexity (O(n)). For a balanced tree, the space complexity is (O(\log n)).

Try our interview co-pilot at AlgoAdvance.com