Binary Tree Upside Down

Imagine you have a binary tree that you want to reorient so it looks like it's been flipped upside down. This problem involves transforming a binary tree structure by changing the parent-child relationships of nodes. Understanding how to manipulate tree structures in this way is fundamental to many tree-based algorithms and data structures.

Problem Description

Given the root of a binary tree, you need to rotate the tree such that the original tree is turned upside down. Specifically, you should:

1. Make the leftmost node of the original tree the new root.
2. For every node, its original left child should become its new parent.
3. Its original right child should become its new left child.
4. The original parent should become its new right child.

The goal is to return the root of the transformed binary tree. You should modify the existing tree in-place, if possible, but returning a new root is the primary objective.

Key Requirements:

• The structure of the tree must be altered as described.
• The original parent-child relationships are reversed in a specific manner.
• The function should return the new root of the upside-down tree.

Edge Cases to Consider:

• An empty tree (null root).
• A tree with only one node.
• A tree where nodes only have a left child or only a right child.

Examples

Example 1:

Input:
    1
   / \
  2   3
 / \
4   5

Output:
    4
   / \
  2   1
 / \
5   3

Explanation:
The leftmost node '4' becomes the new root.
- Node '2' was the parent of '4'. In the new tree, '4' becomes the parent of '2' (as its left child). '1' becomes the right child of '2'.
- Node '5' was the right child of '2'. In the new tree, '5' becomes the left child of '2'.
- Node '3' was the right child of '1'. In the new tree, '3' becomes the right child of '1'.

Example 2:

Input:
    1
   /
  2
 /
3

Output:
    3
   /
  2
 /
1

Explanation:
The leftmost node '3' becomes the new root.
- Node '2' was parent of '3', now '3' is parent of '2' (left child). '1' becomes right child of '2'.
- Node '1' was parent of '2', now '2' is parent of '1' (left child).

Example 3:

Input:
    1
     \
      2
       \
        3

Output:
    1
     \
      2
       \
        3

Explanation:
This tree has no leftmost nodes other than the root itself. The transformation results in the same tree structure because there are no left children to promote.

Constraints

• The number of nodes in the tree will be between 0 and 1000.
• Node values will be integers within a reasonable range (e.g., -1000 to 1000).
• The tree structure can be skewed (e.g., a linked list).
• Your solution should aim for an efficient time complexity, ideally O(N), where N is the number of nodes.

Notes

Consider how you will traverse the tree to rearrange the pointers. A recursive or iterative approach might be suitable. Pay close attention to how you manage the temporary storage of parent and child pointers as you modify the tree. You may find it helpful to think about the process of moving from one node to its new position.