Description
Swap the left and right children of every binary-tree node. Trees in examples use level-order arrays with null for missing children.
Solution
import sys
sys.setrecursionlimit(100_000)
def invert_tree(root):
if root:
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return rootExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,1,3]]- Output
[2,3,1]
The two child positions are exchanged.
Example 2
- Input
[[]]- Output
[]
An empty tree stays empty.
Example 3
- Input
[[4]]- Output
[4]
A leaf has no children to swap.
Approach
Recursively invert both child subtrees and exchange them.
Time & space
O(n) time; O(h) recursion space for n nodes and height h.