Invert Binary Tree LeetCode Solution

Problem Statement:

Invert Binary Tree LeetCode Solution – In this question, Given a root of any binary tree, the solution is required to invert the binary tree meaning the left tree should become the right tree and vice versa.

Explanation

We can ask ourselves which tree traversal would be best to invert the binary tree. Preorder is a pretty simple and readable solution. Our solution would be recursive.  Here are the steps :

1. The function will take root as an argument.
2. Swap root of left and right subtree.
3. invert left binary subtree.
4. invert right binary subtree.
5. return root once every subtree is inverted.

Iterative Version

Here we can use a Preorder Traversal to traverse the tree (same idea if you prefer Inorder, but you’ll need to modify the code a little bit). First, you construct a stack to store TreeNode*s and pop out one at a time to process it. if the stack is empty, which means even the up-most root node and its right node is processed, then we can safely jump out of the loop. The only point is that when we’ve done the swap, we were supposed to do t = t->right, but here since we’ve swapped the left and the right node, the right should be currently the left node.

Python Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

Java Solution:

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
    public TreeNode invertTree(TreeNode root) {
      if (root == null){
          return root;
      }
      TreeNode temp = root.left;
      root.left = root.right;
      root.right = temp;
      invertTree(root.left);
      invertTree(root.right);
      return root;
    }
}

Time complexity for Invert Binary Tree LeetCode Solution:

O(N)

We will visit each node only once so O(N) would be the Time complexity.

Space Complexity:

O(N)

In the worst case, if the binary tree is a skewed tree(only one child), the recursion call stack would need O(N) memory.