LeetCode 156: Binary Tree Upside Down Solution in Python Explained

Problem Statement

In LeetCode 156, you’re given the root of a binary tree with a specific property: all right nodes are either leaf nodes (no children) or null, and left nodes form a chain leading to the leftmost node. Your task is to transform the tree by making the leftmost node the new root, adjusting pointers so original parents become right children and right siblings become left children, returning the new root. This differs from stack design like LeetCode 155: Min Stack, focusing on tree restructuring rather than data structure operations.

Constraints

• Number of nodes: 0 <= n <= 10^5
• Node values: -1000 <= Node.val <= 1000
• Right nodes are leaves or null

Example

Let’s see some cases:

Copy codeInput: root = [1,2,3,4,5]
      1
     / \
    2   3
   /
  4
 /
5
Output: [5,4,2,null,null,3,1]
      5
     / \
    4   null
   / \
  2   null
 / \
3   1
Explanation: Leftmost 5 becomes root, 4→right of 5, 2→right of 4, etc.

Copy codeInput: root = []
Output: null
Explanation: Empty tree, return null.

Copy codeInput: root = [1,2,null,3]
      1
     /
    2
   /
  3
Output: [3,2,null,1]
      3
     /
    2
   /
  1
Explanation: 3 becomes root, 2→right of 3, 1→left of 2.

These examples show we’re flipping the tree upside down.

Understanding the Problem

How do you solve LeetCode 156: Binary Tree Upside Down in Python? Take root = [1,2,3,4,5]. Originally structured as a left-leaning tree with right leaves, we need 5 as the new root, 4 as its right child, 2 as 4’s right child, and so on, adjusting pointers: 5→4→2→3→1. For [1,2,null,3], 3 becomes the root. This isn’t an array search like LeetCode 154: Find Minimum in Rotated Sorted Array II; it’s about tree transformation. We’ll use: 1. Iterative Left-Rotation: O(n) time, O(1) space—our best solution. 2. Recursive Left-Rotation: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Iterative Left-Rotation Approach

Explanation

Iterative Left-Rotation transforms the tree by iterating from the root down the left chain, rotating each node:

• For each node, save its left child, right child, and parent.
• Make the left child the new root, set its right to the current node, and its left to the current node’s right.
• Update pointers iteratively, avoiding recursion.

This is the best solution due to its O(n) time complexity, O(1) space usage (no recursion stack), and straightforward pointer adjustments, making it efficient and space-optimal.

For [1,2,3,4,5]:

• Start at 1, rotate with 2.
• Move to 2, rotate with 4.
• Move to 4, rotate with 5.
• Result: 5→4→2→3→1.

Step-by-Step Example

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

Example 1: root = [1,2,3,4,5]

Goal: Return [5,4,2,null,null,3,1].

• Start: curr = 1, prev = None, prev_right = None.
• 1: left=2, right=3.
• Step 1: curr = 1.
• Save: left = 2, right = 3.
• curr.left = prev_right → 1.left=None.
• curr.right = prev → 1.right=None.
• prev = curr → prev = 1.
• prev_right = right → prev_right = 3.
• curr = left → curr = 2.
• Step 2: curr = 2.
• Save: left = 4, right = None.
• 2.left=3, 2.right=1.
• prev = 2, prev_right = None, curr = 4.
• Step 3: curr = 4.
• Save: left = 5, right = None.
• 4.left=None, 4.right=2.
• prev = 4, prev_right = None, curr = 5.
• Step 4: curr = 5.
• Save: left = None, right = None.
• 5.left=None, 5.right=4.
• prev = 5, curr = None.
• Finish: Return prev = 5.

Example 2: root = []

Goal: Return null.

• Start: curr = None, return None.
• Finish: Return null.

Example 3: root = [1,2,null,3]

Goal: Return [3,2,null,1].

• Start: curr = 1.
• Step 1: curr = 1.
• 1.left=2, 1.right=None.
• 1.left=None, 1.right=None.
• prev = 1, curr = 2.
• Step 2: curr = 2.
• 2.left=3, 2.right=None.
• 2.left=None, 2.right=1.
• prev = 2, curr = 3.
• Step 3: curr = 3.
• 3.left=None, 3.right=2.
• prev = 3, curr = None.
• Finish: Return 3.

How the Code Works (Iterative Left-Rotation) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def upsideDownBinaryTree(root: TreeNode) -> TreeNode:
    # Line 1: Handle null or leaf case
    if not root or not root.left:
        # If empty or no left child (e.g., [] or leaf), return as is
        return root

    # Line 2: Initialize pointers
    curr = root
    # Current node (e.g., 1)
    prev = None
    # Previous parent (e.g., None)
    prev_right = None
    # Previous right child (e.g., None)

    # Line 3: Iterate down left chain
    while curr:
        # Continue until null (e.g., 1→2→4→5)

        # Line 4: Save current children
        left = curr.left
        # Left child (e.g., 2 for 1)
        right = curr.right
        # Right child (e.g., 3 for 1)

        # Line 5: Reassign pointers
        curr.left = prev_right
        # Left becomes prev right (e.g., 1.left=None)
        curr.right = prev
        # Right becomes prev (e.g., 1.right=None)

        # Line 6: Update pointers for next iteration
        prev = curr
        # Prev becomes current (e.g., 1)
        prev_right = right
        # Prev right becomes current right (e.g., 3)
        curr = left
        # Move to left child (e.g., 2)

    # Line 7: Return new root
    return prev
    # Last prev is new root (e.g., 5)

This detailed breakdown clarifies how iterative left-rotation efficiently flips the tree.

Alternative: Recursive Left-Rotation Approach

Explanation

Recursive Left-Rotation recursively processes the left chain:

• Base case: Return the node if no left child.
• Recurse on the left child, then reassign pointers to make it the new root.

It’s a practical alternative, also O(n) time, but uses O(n) space for the recursion stack, less space-efficient than iteration.

For [1,2,3,4,5]:

• Recurse to 5, build up: 5→4→2→3→1.

Step-by-Step Example (Alternative)

For [1,2,3,4,5]:

• Step 1: root = 1, recurse on 2.
• Step 2: Recurse to 4, then 5 (base).
• Step 3: Build: 5.right=4, 4.right=2, 2.left=3, 2.right=1.
• Finish: Return 5.

How the Code Works (Recursive)

Copy codedef upsideDownBinaryTreeRecursive(root: TreeNode) -> TreeNode:
    if not root or not root.left:
        return root
    new_root = upsideDownBinaryTreeRecursive(root.left)
    root.left.left = root.right
    root.left.right = root
    root.left = None
    root.right = None
    return new_root

Complexity

• Iterative Left-Rotation:
• Time: O(n) – single pass down left chain.
• Space: O(1) – constant space.
• Recursive Left-Rotation:
• Time: O(n) – recursive traversal.
• Space: O(n) – recursion stack.

Efficiency Notes

Iterative Left-Rotation is the best solution with O(n) time and O(1) space, offering efficiency and minimal memory—Recursive Left-Rotation matches time complexity but uses O(n) space due to recursion, making it elegant but less space-efficient.

Key Insights

• Left Chain: Drives transformation.
• Iteration: Space-efficient.
• Recursion: Intuitive but costly.

Additional Example

For [2,3,null,4]:

• Goal: [4,3,null,2].
• Iterative: 4.right=3, 3.right=2.

Edge Cases

• Empty Tree: [] → null.
• Single Node: [1] → [1].
• Right Leaf: [1,null,2] → [1,null,2].

Both solutions handle these well.

Final Thoughts

LeetCode 156: Binary Tree Upside Down in Python is a unique tree transformation challenge. The Iterative Left-Rotation solution excels with its space efficiency and clarity, while Recursive Left-Rotation offers a recursive approach. Want more? Try LeetCode 145: Binary Tree Postorder Traversal for tree basics or LeetCode 148: Sort List for list skills. Ready to practice? Solve LeetCode 156 on LeetCode with [1,2,3,4,5], aiming for [5,4,2,null,null,3,1]—test your skills now!