Given the root of a binary tree, invert it.
Given the following two binary trees:
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.
Here is what our algorithm will look like:
Since we traverse each node once, the solution will take O(N) time where 'N' is the total number of nodes in the tree.
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.