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.

See Approach 1

Complexity:

• Time Complexity: O(n), since each node is visited by the tree once.

• Space Complexity: O(n)