Binary Tree Inversion

Difficulty Level: $\mathtt{EASY}$ @ This is a LeetCode question found HERE

What is Tree Inversion?

Tree Inversion means to swap all the left and right child for all the nodes in the tree. Following picture should explain this:

Solution

The solution is itself obvious from the definition of inversion itself. We need to swap the children of each of the node. Therefore we need to traverse through each of the node and swap their children. So the time complexity is going to $\cal{\theta(n)}$, $n$ being the number of nodes in the tree.

This can be solved either Recursively or Iteratively. In either way, we traverse through all the nodes and swap the children.

Following is the implementation for both the methods.

Complexity

In both the methods we visit each of the node once and swap the children. Swapping actions is constant time. $\therefore$ The time complexity is $\cal{O(n)}$.

As of space, both the method will mainain a stack of nodes. $\therefore$ The space complexity is also $\cal{O(n)}$.

---

---

---