invert-bin-tree

Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/

Solution 1: Recursion

• Complexity: $O(n)$ as each node is iterated once. $O(\lg n)$ call stack depth.

if not root:
    return None
root.left  = self.invertTree(root.right)
root.right = self.invertTree(root.left)
return root

Solution 2: Iteration

Implemented with deque.

if not root:
    return None
 
queue = collections.deque([root])
while queue:
    current = queue.popleft()
    current.left, current.right = current.right, current.left
    
    if current.left:
        queue.append(current.left)
    
    if current.right:
        queue.append(current.right)
 
return root

Implements level-order.