## 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)*