Recursively invert subtrees, then swap:
function invertTree(root):
if root == null:
return null
left = invertTree(root.left)
right = invertTree(root.right)
root.left = right
root.right = left
return root
Or swap first, then recurse. Both work:
function invertTree(root):
if root == null:
return null
temp = root.left
root.left = root.right
root.right = temp
invertTree(root.left)
invertTree(root.right)
return root
Time: . Space: .
The order doesn't matter because swapping at one level is independent of swapping at other levels.