Invert Binary Tree

Problem Summary

• Given the root of the tree, for each node, swap the left child with right child

Why This Works

• For each node, we call invert on left and right child
• Save the result as the other child

Main Concepts Used

• Trees
• Depth First Search
• Depth First Traversal
• Tree Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason:
• Space: $O(h)$ → Reason: Height of the tree for the call-stack, in one sided tree it would be $O(n)$

Code

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

Common Mistakes / Things I Got Stuck On

• Over complicating the root of the tree by repeating swaps and calling helper for each child
• Over complicating by creating a helper function in the first place