Invert Binary Tree

Invert a binary tree. Left and right subtrees exchange.

Question

Invert a binary tree. Left and right subtrees exchange.

Example:

Input: {1,3,#}
Output: {1,#,3}
Explanation:
	  1    1
	 /  =>  \
	3        3

Input: {1,2,3,#,#,4}
Output: {1,3,2,#,4}
Explanation: 
	
      1         1
     / \       / \
    2   3  => 3   2
       /       \
      4         4

Analyzation

Recursion

IMPORTANT TEMPLATE!!

All problems including “Invert”, “Reverse”, can potentially use the swap pattern. See code below as the template.

The Code

def invertBinaryTree(self, root):
        # write your code here
        if root is None:
            return
        
        temp = root.left
        root.left = root.right
        root.right = temp
        
        self.invertBinaryTree(root.left)
        self.invertBinaryTree(root.right)

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).