Problem statement

https://leetcode.com/problems/binary-tree-upside-down/

Solution

What we need to understand here is that input tree has very special structure, it is very similar to single-linked list, but with some extra branches. The idea is very similar to problem problem 0206. Reverse Linked List.

There are two main ways how you can solve this problem: recursively or iteratively. Here is the code for iterative solution, which will not use any additional memory.

Complexity

Time complexity is $\mathcal{O}(n)$, where $n$ is total number of nodes in tree, space complexity is $\mathcal{O}(1)$.

Code

class Solution:
    def upsideDownBinaryTree(self, root):
        tmp, prv, curr = None, None, root
        while curr:
            nxt = curr.left
            
            curr.left = tmp
            tmp = curr.right
            curr.right = prv
            
            prv = curr
            curr = nxt
            
        return prv