Problem Statement
Given the root of a binary tree, invert it.
Example:
Given the following two binary trees:
Constraints:
- The number of nodes in both trees is in the range
[0, 100]. - -100 <= Node.val <= 100
Why this is a Multi-threaded problem
| What the question says | The signal it matches |
|---|---|
| "Given the root of a binary tree, invert it" | each subtree is rewritten independently |
| "The number of nodes in both trees is in the range [0, 100]" | the parts never share the nodes they write |
This is the transform a structure variant: each subtree is rewritten independently.
The closest alternative. The plain recursion again, and again it wins at this size. A queue-based level walk is a third correct answer and is the one to give if recursion depth is a concern.
This problem differs from Same Tree in one way that matters for threads: it writes. Reading in parallel is always safe, and writing is only safe when no two threads touch the same memory. Here they do not, because each call swaps the children of one node and then hands two separate subtrees to its own calls. Nothing above is read again, so no lock is needed. That is the property to state out loud, because it is what a concurrency question is really asking about.
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.