Solution: Invert Binary Tree

Statement#

Given the root node of a binary tree, transform the tree by swapping each node’s left and right subtrees, thus creating a mirror image of the original tree. Return the root of the transformed tree.

Constraints:

• $0\leq$ Number of nodes in the tree $\leq 100$
• $-1000 \leq$ Node.value $\leq 1000$

Solution#

For this solution, we do a post-order (left, right, parent) traversal of the binary tree. The algorithm is as follows:

• Perform post-order traversal on the left child of the root node.
• Perform post-order traversal on the right child of the root node.
• Swap the left and right children of the root node.

Since we perform a depth-first search traversal, the children of any node are already mirrored even before we return the node itself.

Let’s look at an example below:

Note: In this example, the node at the top of the stack is the current node.

Time complexity#

The time complexity of this solution is linear, $O(n)$, where $n$ is the number of nodes in the tree.

Note: Every subtree needs to be mirrored, so we visit every node once. Because of that, the runtime complexity is $O(n)$.

Space complexity#

The space complexity of this solution is $O(h)$, where $h$ is the height of the tree. This is because our recursive algorithm uses space on the call stack, which can grow to the height of the binary tree. The complexity will be $O(\log n)$ for a balanced tree and $O(n)$ for a degenerate tree.