Question: Invert a binary tree.
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Solution
Approach 1: Recursive
The inverse of an empty tree is the empty tree. The inverse of a tree with root r, and subtrees right and left, is a tree with root r, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.
Complexity:
Time Complexity: O(n), since each node is visited by the tree once.
Space Complexity: O(n)