Problem statement

https://binarysearch.com/problems/Tree-Shifting/

Solution

First use bfs to create levels of tree. Then start form the last layer and try to attach nodes from right to left, first as right children, then as left children.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        if not root: return root
        queue, levels = deque([root]), []
        
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node)
                if node.left:  queue.append(node.left)
                if node.right: queue.append(node.right)
            levels.append(level)

        levels += [[]]
        for x in range(len(levels) - 2, -1, -1):
            row = levels[x + 1]
            for node in levels[x][::-1]:
                node.right = row.pop() if row else None
                node.left = row.pop() if row else None

        return root