Invert Binary Tree - Leetcode Python Solution

 Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Iterative approcah . 

# 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: TreeNode) -> TreeNode:

        if not root:

            return None

        q = []

        q.append(root)

        while q:

            curr = q.pop()

            curr.left , curr.right = curr.right,curr.left

            if curr.left:

                q.append(curr.left)

            if curr.right:

                q.append(curr.right)

        return root

            

        TC: O(n)

        SC: O(n) in worst case where queue is completely occupied. 

Recursive approch:

# 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: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        curr.left,curr.right = curr.right,curr.left

        return root

            

    Recursive approach:

# 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: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        curr.left,curr.right = curr.right,curr.left

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        return root

            

       TC: O(n)

       SC: O(n)