Problem Statement

Given the root of a binary tree, invert it.

Example:

Given the following two binary trees:

Solution

This problem is quite similar to Same Tree. We can follow the same approach. After swapping left and right child of a node, we will recursively invert its left and right subtrees.

Code

Here is what our algorithm will look like:

Time Complexity

Since we traverse each node once, the solution will take O(N) time where 'N' is the total number of nodes in the tree.

Space Complexity

We will need O(N) space for the recursion stack in the worst case (when the binary tree is a list). Overall, we will need to store nodes equal to the height of the tree, hence, O(H) space complexity, where H is the height of the given tree.

Making the Algorithm Multi-threaded

To further improve the algorithm, we can make invertTree() multi-threaded to invert left and right subtrees in separate threads.

We can find how many cores the machine has on which our algorithm is running. We will, then, start multiple threads so that each core can run one thread.

Here is the code that takes care of this scenario:

Time and Space Complexities

Everything has the same complexity as the previous solution.