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 left:
- Invert right:
invert(7)- Invert left:
invert(6)→ returns 6 - Invert right:
invert(9)→ returns 9 - Swap: 7's children become (9, 6)
- Invert left:
- Swap: 4's children become (7, 2)
Result: 4(7(9,6), 2(3,1)).
Visit each node once. time. Recursion stack depth is tree height. space, worst case for skewed tree.