LeetCode 226 Invert Binary Tree - Example and Complexity Analysis

Trace the tree 4(2(1,3), 7(6,9)).

Call invert(4):

• Invert left: invert(2)
  • Invert left: invert(1) → returns 1 (leaf, no children to swap)
  • Invert right: invert(3) → returns 3
  • Swap: 2's children become (3, 1)
• Invert right: invert(7)
  • Invert left: invert(6) → returns 6
  • Invert right: invert(9) → returns 9
  • Swap: 7's children become (9, 6)
• Swap: 4's children become (7, 2)

Result: 4(7(9,6), 2(3,1)).

Visit each node once. $O(n)$ time. Recursion stack depth is tree height. $O(h)$ space, worst case $O(n)$ for skewed tree.