Invert a binary tree by swapping the left and right children of every node.

Example 1:

• Input: root = [4,2,7,1,3,6,9]
• Output: [4,7,2,9,6,3,1]

Example 2:

• Input: root = [2,1,3]
• Output: [2,3,1]

Constraints:

• 0 ≤ tree nodes ≤ 100

Tests recursive tree transformation. Made famous by a Google interview story.

Pattern: Tree Transformation

Solve for children first (post-order), then transform the current node.

graph TD
    Root["TreeNode (Root)"] -->|Recurse Left| Left["Left Subtree"]
    Root -->|Recurse Right| Right["Right Subtree"]
    Left --> Base1{"Base Case (null)"}
    Right --> Base2{"Base Case (null)"}
    Base1 --> Combine["Combine Results"]
    Base2 --> Combine
    Combine --> Ans["Return Root Value / Depth"]

// Recursive is standard

• Time Complexity: O(n)
• Space Complexity: O(h)
• Explanation: Recursive post-order swap.

function invertTree(root) {
  if (!root) return null;
  const temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);
  return root;
}

• Time Complexity: O(n)
• Space Complexity: O(h)
• Explanation: Recursive post-order inversion.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

1. Go down to leaves first (post-order)
2. Swap at each level as you return
3. Tree remains valid — just mirrored

1. Swap left and right children.
2. Recursively invert subtrees before swapping.
3. Base case: null returns null.

👉 Solve this problem interactively in the DSA Lab