# LeetCode 156: Binary Tree Upside Down

## Problem Restatement

We are given the root of a binary tree.

We need to flip the tree upside down and return the new root.

The transformation follows these rules:

1. The original left child becomes the new root of that local subtree.
2. The original root becomes the new right child.
3. The original right child becomes the new left child.

The operation is done level by level.

The input has an important guarantee: every right node has a sibling and has no children. In older wording, all right nodes are either leaf nodes with a left sibling or empty. This guarantee makes the flip well-defined.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | New root after flipping the tree |
| Main structure | The left spine becomes the new main path |
| Right-node guarantee | Right children are leaves with left siblings or empty |

Example function shape:

```python
def upsideDownBinaryTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    ...
```

## Example

Input tree:

```text
    1
   / \
  2   3
 / \
4   5
```

Level-order form:

```python
[1, 2, 3, 4, 5]
```

After flipping:

```text
    4
   / \
  5   2
     / \
    3   1
```

Level-order form:

```python
[4, 5, 2, None, None, 3, 1]
```

The old leftmost node `4` becomes the new root.

The old right child `5` becomes the left child of `4`.

The old parent `2` becomes the right child of `4`.

Then the same pattern continues upward.

## First Thought: Understand One Local Flip

Consider a small tree:

```text
  root
  /  \
 L    R
```

After flipping this local shape:

```text
   L
  / \
 R   root
```

So the pointer changes are:

```python
L.left = R
L.right = root
root.left = None
root.right = None
```

For a full tree, we apply this from the bottom of the left spine upward.

That means recursion is natural: first flip the left subtree, then rewire the current root below its left child.

## Key Insight

The new root is always the leftmost node of the original tree.

For example:

```text
    1
   /
  2
 /
4
```

After flipping, `4` becomes the root.

So recursion should go left until it reaches the leftmost node.

Base case:

```python
if root is None or root.left is None:
    return root
```

Then as recursion returns, each old parent is attached as the right child of its old left child.

## Algorithm

Use recursive DFS.

For each node `root`:

1. If `root` is empty or has no left child, return `root`.
2. Recursively flip `root.left`.
3. Let the original left child receive new children:
   - `root.left.left = root.right`
   - `root.left.right = root`
4. Clear the old root pointers:
   - `root.left = None`
   - `root.right = None`
5. Return the new root from the recursion.

## Walkthrough

Use:

```text
    1
   / \
  2   3
 / \
4   5
```

Start at `1`.

Before flipping `1`, we first flip its left subtree rooted at `2`.

At node `2`, before flipping it, we first flip its left subtree rooted at `4`.

Node `4` has no left child, so it becomes the new root.

Now unwind to node `2`.

Original local shape:

```text
  2
 / \
4   5
```

Rewire:

```python
4.left = 5
4.right = 2
2.left = None
2.right = None
```

Now we have:

```text
  4
 / \
5   2
```

Then unwind to node `1`.

Original local shape around `1`:

```text
  1
 / \
2   3
```

Now `2` is already below `4`, but it is still the old left child of `1`.

Rewire:

```python
2.left = 3
2.right = 1
1.left = None
1.right = None
```

Final tree:

```text
    4
   / \
  5   2
     / \
    3   1
```

## Correctness

The algorithm reaches the leftmost node first. That node has no left child, so it must become the new root after the upside-down transformation.

Now consider any original node `root` with left child `L` and right child `R`.

By the time recursion returns to `root`, the subtree rooted at `L` has already been flipped correctly, and `L` is positioned as the place where `root` should be attached.

The required local transformation says:

```python
L.left = R
L.right = root
```

The algorithm performs exactly these assignments:

```python
root.left.left = root.right
root.left.right = root
```

Then it clears:

```python
root.left = None
root.right = None
```

This prevents old pointers from forming cycles.

Because the algorithm performs the correct local transformation for every node on the left spine, from bottom to top, the entire tree is flipped correctly.

## Complexity

Let `n` be the number of nodes and `h` be the height of the tree.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is processed once |
| Space | `O(h)` | Recursion stack follows the height of the tree |

## Implementation

```python
# 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 upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None or root.left is None:
            return root

        new_root = self.upsideDownBinaryTree(root.left)

        root.left.left = root.right
        root.left.right = root

        root.left = None
        root.right = None

        return new_root
```

## Code Explanation

The base case handles an empty tree or a node with no left child:

```python
if root is None or root.left is None:
    return root
```

A node with no left child becomes the top of the flipped subtree.

This line flips the left subtree first:

```python
new_root = self.upsideDownBinaryTree(root.left)
```

After that call returns, `new_root` is the leftmost node of the original subtree.

Now we rewire the old left child:

```python
root.left.left = root.right
root.left.right = root
```

The old right child becomes the new left child.

The old root becomes the new right child.

Then we remove the old links:

```python
root.left = None
root.right = None
```

Finally, we return the same new root all the way up:

```python
return new_root
```

## Iterative Version

We can also do the same transformation while walking down the left spine.

```python
class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        prev_root = None
        prev_right = None

        while root:
            next_root = root.left
            next_right = root.right

            root.left = prev_right
            root.right = prev_root

            prev_root = root
            prev_right = next_right
            root = next_root

        return prev_root
```

Here:

| Variable | Meaning |
|---|---|
| `prev_root` | The parent already flipped below the current node |
| `prev_right` | The old right child that should become the new left child |
| `next_root` | The next node on the old left spine |

This version uses constant extra space.

## Testing

```python
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    if not root:
        return []

    q = [root]
    out = []

    while q:
        node = q.pop(0)

        if node:
            out.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
            out.append(None)

    while out and out[-1] is None:
        out.pop()

    return out

def run_tests():
    sol = Solution()

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )

    new_root = sol.upsideDownBinaryTree(root)
    assert level_order(new_root) == [4, 5, 2, None, None, 3, 1]

    assert sol.upsideDownBinaryTree(None) is None

    single = TreeNode(1)
    assert level_order(sol.upsideDownBinaryTree(single)) == [1]

    root = TreeNode(1, TreeNode(2), TreeNode(3))
    assert level_order(sol.upsideDownBinaryTree(root)) == [2, 3, 1]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 5]` | Main example |
| Empty tree | Handles `None` |
| Single node | Base case |
| `[1, 2, 3]` | Smallest non-trivial flip |